Unit 5: Graph Theory-II

Graph theory studies networks of vertices joined by edges; this unit builds on basic graph terminology (originating with Euler's 1736 Königsberg bridges problem) to classify graphs by the special walks they admit, by whether they can be drawn in the plane, and by how few colours suffice to distinguish adjacent parts. Every result below depends on the following conventions.

• Graph: a pair G = (V, E) where V is a set of vertices and E a set of edges joining vertex pairs; here graphs are simple (no loops, no multiple edges) and undirected unless stated.
• Degree: deg(v) is the number of edges incident to v; the handshaking lemma gives Σ deg(v) = 2|E|, so the number of odd-degree vertices is always even.
• Walk, trail, path: a walk is any vertex-edge sequence; a trail repeats no edge; a path repeats no vertex.
• Circuit and cycle: a circuit is a closed trail; a cycle is a closed path.
• Connected: a graph is connected if some path joins every pair of vertices.
• Notation for families: Kₙ = complete graph on n vertices; Kₘ,ₙ = complete bipartite graph; Cₙ = cycle on n vertices.

II. Eulerian Graphs — Traversing Every Edge

An Eulerian traversal crosses each edge exactly once; the theory answers exactly when this is possible, resolving Euler's original bridge puzzle.

A. Eulerian graphs

A graph is Eulerian when it contains a closed trail using every edge.

• Euler circuit: a closed trail that includes every edge of G exactly once and returns to its start.
• Euler path (semi-Eulerian): an open trail using every edge exactly once but starting and ending at different vertices.
• Eulerian graph: a connected graph possessing an Euler circuit; e.g. C₄ and any cycle Cₙ are Eulerian since every vertex has degree 2.
• Königsberg bridges: modelled as a multigraph with four vertices all of odd degree, so no Euler circuit or path exists — the historical origin of the theory.

B. Euler theorem

The theorem gives a purely degree-based test, avoiding trial traversal.

• Statement (circuit): a connected graph has an Euler circuit if and only if every vertex has even degree.
• Statement (path): a connected graph has an Euler path if and only if it has exactly two vertices of odd degree; the path must begin at one odd vertex and end at the other.
• Reason: each visit to an intermediate vertex uses one edge to enter and one to leave, consuming degree in pairs, so an even degree is required at every through-vertex.
• Worked example: K₅ has every vertex of degree 4 (even) and is connected, so it has an Euler circuit. K₄ has every vertex of degree 3 (all odd, four odd vertices) so it has neither an Euler circuit nor an Euler path.

III. Hamiltonian Graphs — Visiting Every Vertex

Where Euler concerns edges, Hamilton concerns vertices; no simple degree criterion exists, only sufficient conditions.

A. Hamiltonian graphs

A graph is Hamiltonian when it contains a spanning cycle through all vertices.

• Hamiltonian cycle: a cycle passing through every vertex exactly once, returning to the start; Cₙ is trivially Hamiltonian.
• Hamiltonian path: a path visiting every vertex exactly once without necessarily closing.
• No known easy test: deciding Hamiltonicity is NP-complete, unlike the Eulerian case.
• Dirac's condition (sufficient): if n ≥ 3 and deg(v) ≥ n/2 for every vertex, G is Hamiltonian.
• Ore's condition (sufficient): if deg(u) + deg(v) ≥ n for every pair of non-adjacent vertices u, v, then G is Hamiltonian.
• Contrast with Eulerian: K₄ is Hamiltonian (cycle 1-2-3-4-1) yet not Eulerian; a graph can be one, both, or neither.

IV. Planar Graphs — Drawing Without Crossings

Planarity asks whether a graph can be drawn in the plane so that edges meet only at vertices, controlling structure through Euler's formula and Kuratowski's characterisation.

A. planar graphs

A planar graph admits a crossing-free drawing in the plane.

• Definition: G is planar if it can be embedded in the plane with no two edges intersecting except at shared endpoints.
• Planar vs plane graph: "planar" means such a drawing exists; a "plane graph" is one already drawn that way.
• Examples: K₄ is planar (redraw one edge outside the triangle); every tree and every cycle is planar.

B. maps

A map is the specific plane embedding under study.

• Map: a particular planar drawing of a connected planar graph, partitioning the plane into pieces.
• Use: the four-colour problem is stated over maps, where countries correspond to regions and shared borders to adjacency.

C. regions

Regions are the areas a plane drawing carves out.

• Region (face): a connected area of the plane bounded by edges; includes the single unbounded outer region.
• Degree of a region: the number of edges on its boundary; a bridge is counted twice because both sides border the same region.
• Sum of region degrees: Σ deg(regions) = 2|E|, mirroring the handshaking lemma.
• Example: a triangle K₃ drawn in the plane has 2 regions — the inside and the outer region.

D. Euler formula

Euler's formula ties vertices, edges and regions together for any connected plane graph.

V - E + R = 2

• Symbols: V = number of vertices, E = number of edges, R = number of regions (faces), including the outer one.
• Consequence (simple planar, V ≥ 3): E ≤ 3V - 6, since each region is bounded by at least 3 edges.
• Triangle-free consequence: if G has no 3-cycles, E ≤ 2V - 4.
• Worked example: K₄ has V = 4, E = 6; then R = 2 - V + E = 4, and E = 6 ≤ 3(4) - 6 = 6, confirming planarity at the bound.

E. non planar graphs

Non-planar graphs cannot be drawn without crossings, detectable via the edge bounds.

• Definition: a graph with no crossing-free plane embedding.
• K₅: V = 5, E = 10; the bound 3V - 6 = 9 < 10, so K₅ is non-planar.
• K₃,₃: V = 6, E = 9; being triangle-free, the bound 2V - 4 = 8 < 9, so K₃,₃ is non-planar (the utilities problem).
• Note: the bounds detect non-planarity but passing them does not guarantee planarity.

F. Kuratowski's theorem (without proof)

The theorem characterises planarity exactly through two forbidden graphs.

• Statement: a graph is planar if and only if it contains no subgraph that is a subdivision of K₅ or K₃,₃.
• Subdivision: the graph obtained by inserting degree-2 vertices along edges; such insertions do not change planarity.
• Significance: K₅ and K₃,₃ are the two minimal non-planar "obstructions"; every non-planar graph hides one of them.

V. Graph Coloring — Separating Adjacent Vertices

Colouring assigns labels to vertices so neighbours differ, measuring structural conflict through the chromatic number.

A. graph coloring

Proper colouring keeps adjacent vertices in distinct colour classes.

• Proper vertex colouring: an assignment of colours to vertices such that no edge joins two vertices of the same colour.
• k-colourable: G can be properly coloured with at most k colours.
• Colour class: the set of all vertices sharing one colour; each class is an independent set (no internal edges).

B. chromatic number of a graph

The chromatic number quantifies the minimum colours required.

• Definition: χ(G) is the least k for which G is k-colourable.
• Basic values: χ(G) = 1 iff G has no edges; χ(G) = 2 iff G is bipartite with at least one edge.
• Cycles: χ(Cₙ) = 2 if n is even, 3 if n is odd.
• Bound: χ(G) ≤ Δ(G) + 1, where Δ(G) is the maximum degree (greedy colouring).
• Four-colour theorem: every planar graph satisfies χ(G) ≤ 4.

C. complete graph and its coloring

The complete graph forces the maximum colour demand.

• Complete graph Kₙ: every pair of vertices is adjacent, so all n vertices are mutually adjacent.
• Chromatic number: χ(Kₙ) = n, since no two vertices may share a colour.
• Edge count: Kₙ has n(n-1)/2 edges, and each vertex has degree n-1.
• Example: K₄ needs 4 distinct colours; it is planar yet uses the full four-colour allowance.

D. regular and bipartite graphs and their coloring

Two structured families with predictable colourings.

1. Regular graphs: every vertex has the same degree r (an r-regular graph).
   • Colouring: χ ≤ r + 1 by the greedy bound; Kₙ is (n-1)-regular needing n colours, hitting this bound.
   • Example: the 3-regular Petersen graph has χ = 3.
2. Bipartite graphs: vertices split into two disjoint sets A, B with every edge joining A to B.
   • Colouring: χ = 2 for any bipartite graph with at least one edge — colour A one colour, B the other.
   • Characterisation: a graph is bipartite iff it contains no odd cycle.
   • Complete bipartite Kₘ,ₙ: all A–B pairs joined, m·n edges, still χ(Kₘ,ₙ) = 2.