Chapter 7: Edges and Cycles

Source: Introduction to Graph Theory, 2nd Edition, by Douglas B. West

Overview

Chapter 7 explores three major topics in graph theory that revolve around edges and cycles: line graphs and edge-coloring, Hamiltonian cycles, and the interplay between planarity, coloring, and cycles. The chapter ties together structural properties of graphs with coloring problems and cycle existence, culminating in deep connections to the Four Color Problem and flow theory.

7.1 Line Graphs and Edge-coloring

Line Graphs

Definition: The line graph L(H) of a graph H has vertex set E(H), with two vertices adjacent in L(H) if and only if the corresponding edges in H share an endpoint.
Line graphs translate edge problems into vertex problems, making them a powerful tool for studying edge-coloring and matchings.

Edge-coloring

Definition: A proper edge-coloring (or proper k-edge-coloring) assigns colors to edges so that no two edges sharing an endpoint receive the same color. The edge-chromatic number (or chromatic index) χ'(G) is the minimum number of colors needed.
Vizing's Theorem (Theorem 7.1.4): For a simple graph G, the edge-chromatic number satisfies Δ(G) ≤ χ'(G) ≤ Δ(G) + 1, where Δ(G) is the maximum degree. This classifies simple graphs into:
- Class 1: χ'(G) = Δ(G)
- Class 2: χ'(G) = Δ(G) + 1
König's Theorem (Theorem 7.1.7): Every bipartite graph is Class 1, i.e., χ'(G) = Δ(G). The proof uses an alternating-path argument to extend partial edge-colorings.
Petersen's Theorem (Theorem 3.3.9, referenced here): Every 2k-regular graph has a 2-factor; combined with König's Theorem, this implies every regular bipartite graph has a 1-factorization.

Key Results on Edge-coloring Bounds

Shannon's Theorem (Theorem 7.1.13): For any graph (including multigraphs), χ'(G) ≤ (3/2) · Δ(G). This is tight.
The Overfull Conjecture states conditions under which a graph is Class 2 based on the existence of an "overfull" subgraph.
Goldberg–Seymour Conjecture (Conjecture 7.1.14): Provides a general upper bound: χ'(G) ≥ Δ(G) + 2 implies χ'(G) equals the maximum of ⌈e(H) / ⌊n(H)/2⌋⌉ over all subgraphs H.

Characterization of Line Graphs (optional)

Krausz's Theorem (Theorem 7.1.16): A simple graph G satisfies L(H) = G for some graph H if and only if E(G) can be decomposed into complete subgraphs with each vertex in at most two.
Beineke's Theorem (Theorem 7.1.18): A simple graph G is a line graph if and only if it contains none of nine specific forbidden induced subgraphs.
van Rooij and Wilf's characterization (Theorem 7.1.17): A simple graph has L(H) = G if and only if G is claw-free and has no double triangle with two odd triangles.
Algorithms exist to test whether a graph is a line graph in linear time (Lehot, 1974).

7.2 Hamiltonian Cycles

Definitions

Definition 7.2.1: A Hamiltonian graph is a graph with a spanning cycle, also called a Hamiltonian cycle.
Definition 7.2.15: A Hamiltonian path is a spanning path.
Named for Sir William Hamilton, who described a game on the dodecahedron. No easily testable characterization is known for Hamiltonian graphs (the problem is NP-complete).

Necessary Conditions

Every Hamiltonian graph is 2-connected (deleting any vertex leaves a connected subgraph).
Proposition 7.2.3: If G has a Hamiltonian cycle, then for every nonempty S ⊆ V, the graph G − S has at most |S| components.
Bipartite graphs: K_m,n is Hamiltonian only if m = n (the cycle must alternate between partite sets).
Toughness (Remark 7.2.6): The toughness t(G) is the maximum t such that G is t-tough. Spanning cycles require toughness at least 1. Chvátal conjectured that sufficiently large toughness is sufficient; the exact value remains open (known to be at least 9/4 by Bauer–Broersma–Veldman, 2000).

Sufficient Conditions

Dirac's Theorem (Theorem 7.2.8): If G is a simple graph with at least 3 vertices and minimum degree δ(G) ≥ n(G)/2, then G is Hamiltonian. This is a cornerstone result; the degree bound is tight.
Ore's Lemma (Lemma 7.2.9): If u, v are distinct nonadjacent vertices with d(u) + d(v) ≥ n(G), then G is Hamiltonian if and only if G + uv is Hamiltonian.
Hamiltonian Closure (Definition 7.2.10): The closure C(G) is obtained by iteratively adding edges between nonadjacent vertices whose degree sum is at least n.
- Bondy–Chvátal Theorem (Theorem 7.2.11): A simple n-vertex graph is Hamiltonian if and only if its closure is Hamiltonian.
- Lemma 7.2.12: The closure is well-defined (independent of the order of edge additions).
Chvátal's Condition (Theorem 7.2.13): Given degree sequence d₁ ≤ ... ≤ d_n with n ≥ 3, if for all i < n/2 we have d_i > i or d_n−i ≥ n − i, then G is Hamiltonian. This is the best possible degree-sequence condition.
Theorem 7.2.17 (Hamiltonian paths): Analogous to Chvátal's condition but for spanning paths, using the transformation G ∨ K₁.
Chvátal–Erdős Theorem (Theorem 7.2.19): If κ(G) ≥ α(G) (connectivity ≥ independence number), then G has a Hamiltonian cycle (unless G = K₂). This connects structural parameters to Hamiltonicity without degree conditions.

Cycles in Directed Graphs (optional)

Definition 7.2.21: A digraph is strict if it has no loops and at most one copy of each ordered pair as an edge.
Ghouila-Houri's Theorem (Theorem 7.2.22): If D is a strict digraph with min{δ⁺(D), δ⁻(D)} ≥ n(D)/2, then D is Hamiltonian. This is the directed analogue of Dirac's Theorem.
Every tournament has a Hamiltonian path (Rédei, 1934). Strong tournaments are Hamiltonian.

Additional Remarks

Long cycles and circumference: The circumference of a graph is the length of its longest cycle. Dirac proved a 2-connected graph with minimum degree k has circumference at least min{n, 2k}.
Remark 7.2.18: Every regular simple graph with vertex degrees at least n(G)/3 is Hamiltonian (Jackson, 1980), with only the Petersen graph preventing a lower threshold.

7.3 Planarity, Colorings, and Cycles

This section connects the Four Color Problem with edge-coloring, Hamiltonian cycles, and introduces flow theory as a generalization.

Tait's Theorem

Definition 7.3.1: A proper face-coloring of a 2-edge-connected plane graph assigns colors to faces so that faces sharing a boundary edge have distinct colors.
Tait's Theorem (Theorem 7.3.2): A simple 2-edge-connected 3-regular plane graph is 3-edge-colorable if and only if it is 4-face-colorable. This links edge-coloring to the Four Color Theorem.
- A proper 3-edge-coloring of a 3-regular graph is called a Tait coloring.
- Tait's Conjecture: Every 3-connected 3-regular planar graph is Hamiltonian. This is equivalent to the Four Color Theorem for 3-regular planar graphs. The conjecture was disproved by Tutte (1946) using the Tutte graph.
Theorem 7.3.4: All 2-edge-connected 3-regular simple planar graphs are 3-edge-colorable if and only if all 3-connected 3-regular simple planar graphs are 3-edge-colorable.
Tutte (1956) proved every 4-connected planar graph is Hamiltonian. Barnette conjectured every planar 3-connected 3-regular bipartite graph is Hamiltonian.

Grinberg's Theorem

Grinberg's Theorem (Theorem 7.3.5): If G is a loopless plane graph with a Hamiltonian cycle C, and G has f_i' faces of length i inside C and f_i faces of length i outside C, then Σ_i (i − 2)(f_i' − f_i) = 0.
This necessary condition is a powerful tool for proving graphs are not Hamiltonian, often using modular arithmetic arguments.
Example 7.3.6: Grinberg's condition applied to the Tutte graph confirms it is not Hamiltonian.

Snarks (optional)

Definition 7.3.7: A bridgeless graph has no cut-edge; a cubic graph is 3-regular.
3-edge-coloring Conjecture (Conjecture 7.3.8, Tutte 1967): Every bridgeless cubic non-3-edge-colorable graph contains a subdivision of the Petersen graph. This has been proved (Robertson–Sanders–Seymour–Thomas, 2001).
Definition 7.3.9: A trivial edge cut isolates a single vertex.
Definition 7.3.11: A snark is a 2-edge-connected 3-regular graph that is not 3-edge-colorable, has girth at least 5, and has no non-trivial 3-edge cut. A prime snark contains no subdivision of a smaller snark.
- The Petersen graph is the only prime snark (proven).
- Dot product (Definition 7.3.12): An operation on cubic graphs that generates new snarks from existing ones.
- Flower snarks (Example 7.3.13): An infinite family of snarks with 4k vertices (for odd k ≥ 5).

Flows and Cycle Covers (optional)

Definition 7.3.14: A flow on a graph G is a pair (D, f) where D is an orientation and f is a weight function satisfying conservation at each vertex. A k-flow has |f(e)| ≤ k − 1 for all edges. A flow is nowhere-zero if f(e) ≠ 0 for all edges.
Proposition 7.3.15: The existence of a nowhere-zero k-flow does not depend on the chosen orientation.
Proposition 7.3.19: A graph has a nowhere-zero 2-flow if and only if it is an even graph (all degrees even).
Proposition 7.3.20 (Tutte, 1949): A cubic graph has a nowhere-zero 3-flow if and only if it is bipartite.
Theorem 7.3.22 (Tutte, 1954): A plane bridgeless graph is k-face-colorable if and only if it has a nowhere-zero k-flow. This extends Tait's theorem by connecting face-coloring to flows.
Theorem 7.3.24: If a cubic graph has a nowhere-zero 4-flow, then it is 3-edge-colorable.
Corollary 7.3.26: A cubic graph is 3-edge-colorable if and only if it has a nowhere-zero 4-flow.
Theorem 7.3.25: A graph has a nowhere-zero 4-flow if and only if it is the union of two even subgraphs.
The 8-flow Theorem (Kilpatrick, 1975; Jaeger, 1979): Every bridgeless graph is 8-flowable. Seymour (1981) improved this to 6-flowable.

Tutte's Flow Conjectures

Tutte's 4-flow Conjecture (Conjecture 7.3.27): Every bridgeless graph containing no subdivision of the Petersen graph is 4-flowable. This implies the Four Color Theorem.
Tutte's 3-flow Conjecture (Conjecture 7.3.28): Every 4-edge-connected graph has a nowhere-zero 3-flow.
Tutte's 5-flow Conjecture (Conjecture 7.3.29): Every bridgeless graph has a nowhere-zero 5-flow.

Cycle Double Covers

Definition 7.3.30: A cover of a graph is a list of subgraphs whose union is G. A double cover has each edge in exactly two subgraphs. A cycle double cover (CDC) consists of cycles.
Only bridgeless graphs have CDCs.
CDC Conjecture (Conjecture 7.3.32, Szekeres 1973, Seymour 1979): Every bridgeless graph has a cycle double cover.
- Related to the Strong Embedding Conjecture: every 2-connected graph embeds on some surface with each face boundary being a single cycle.
Proposition 7.3.33: A graph has a nowhere-zero 4-flow if and only if it has a CDC formed from three even subgraphs.
- Tutte's 4-flow Conjecture implies every graph in P (no Petersen subdivision) has a CDC.

Key Themes and Significance

Edge-coloring classification: Vizing's Theorem provides a tight two-value classification for the chromatic index of simple graphs. Determining which class a graph belongs to is itself NP-complete, motivating the study of sufficient conditions for Class 1 membership.
Hamiltonicity: The search for necessary and sufficient conditions for Hamiltonian cycles is one of graph theory's central problems. The progression from Dirac's simple degree condition through Ore's lemma, Chvátal's optimal degree-sequence condition, and the Chvátal–Erdős connectivity/independence condition illustrates increasingly sophisticated structural approaches.
Planarity-coloring-flow nexus: Section 7.3 reveals deep connections: the Four Color Theorem is equivalent to Tait's conjecture about edge-coloring cubic planar graphs, which is equivalent to the existence of nowhere-zero 4-flows on planar graphs. This equivalence chain motivates the study of flows as a generalization of coloring to non-planar graphs.
The Petersen graph: This graph appears throughout the chapter as a critical example and counterexample — it is not Hamiltonian, not 3-edge-colorable, not 4-flowable, and its role as the unique prime snark makes it central to the 3-edge-coloring conjecture.
Open problems: Several major conjectures remain open or were only recently resolved, including Tutte's flow conjectures and the Cycle Double Cover Conjecture, highlighting active areas of research in structural graph theory.

Key Theorems and Results

Result	Statement
Vizing (7.1.4)	Δ(G) ≤ χ'(G) ≤ Δ(G) + 1 for simple graphs
König (7.1.7)	Every bipartite graph is Class 1: χ'(G) = Δ(G)
Shannon (7.1.13)	χ'(G) ≤ (3/2) · Δ(G) for multigraphs
Dirac (7.2.8)	δ(G) ≥ n/2 ⟹ G is Hamiltonian
Bondy–Chvátal (7.2.11)	G is Hamiltonian ⟺ C(G) is Hamiltonian
Chvátal (7.2.13)	Best possible degree-sequence condition for Hamiltonicity
Chvátal–Erdős (7.2.19)	κ(G) ≥ α(G) ⟹ Hamiltonian cycle exists
Tait (7.3.2)	3-edge-colorable ⟺ 4-face-colorable (for 2-edge-connected cubic plane graphs)
Grinberg (7.3.5)	Σ (i − 2)(f_i' − f_i) = 0 for plane Hamiltonian graphs
Tutte (7.3.22)	k-face-colorable ⟺ nowhere-zero k-flow (for plane bridgeless graphs)

Flags

Introduction to Graph Theory/Edges and Cycles

From charlesreid1

Contents