Study guide

14.2 Graph Theory: Trees, Cycles, Paths, and Planarity

GRE Subject Test: Mathematics Exam

Track your progress as you read

Finished sections get a check mark.

1 Chapter 1: Single-Variable Differential Calculus

1.1 Limits, Continuity, and Epsilon-Delta Definitions 1.2 Differentiation Rules, Implicit & Inverse Differentiation 1.3 Mean Value Theorem, Rolle's Theorem, and Function Extrema 1.4 L'Hôpital's Rule, Curve Sketching, and Optimization 1.5 Functions, Graphs, Transformations, and Inverses 1.6 Trigonometric Functions, Identities, and Equations 1.7 Coordinate Geometry, Lines, Circles, and Conics 1.8 Parametric and Polar Curves

2 Chapter 2: Single-Variable Integral Calculus

2.1 Riemann Sums and the Fundamental Theorem of Calculus 2.2 Advanced Integration Techniques 2.3 Geometric Applications: Areas, Volumes, and Arc Length 2.4 Improper Integrals and Convergence Criteria

3 Chapter 3: Sequences, Infinite Series & Power Series

3.1 Sequences, Monotonicity, and Limits 3.2 Infinite Series and Convergence Tests 3.3 Power Series, Radius and Interval of Convergence 3.4 Taylor and Maclaurin Series with Error Bounds

4 Chapter 4: Multivariable Differential Calculus

4.1 Multivariable Functions, Limits, and Partial Derivatives 4.2 Directional Derivatives, Gradients, and Tangent Planes 4.3 Multivariable Chain Rule and Implicit Differentiation 4.4 Multivariable Extrema, Hessian Matrix, and Lagrange Multipliers

5 Chapter 5: Multivariable Integration & Vector Calculus

5.1 Multiple Integrals in Cylindrical and Spherical Coordinates 5.2 Change of Variables and the Jacobian Determinant 5.3 Vector Fields, Line Integrals, and Green's Theorem 5.4 Surface Integrals, Stokes' Theorem, and the Divergence Theorem

6 Chapter 6: Ordinary Differential Equations

6.1 First-Order ODEs: Separable, Linear, and Exact Equations 6.2 Special First-Order ODEs: Homogeneous, Bernoulli, and Orthogonal Trajectories 6.3 Second-Order Linear Homogeneous ODEs with Constant Coefficients 6.4 Nonhomogeneous Linear ODEs: Undetermined Coefficients and Variation of Parameters

7 Chapter 7: Elementary Algebra & Number Theory

7.1 Elementary Algebra, Polynomials, Roots, and Factorization 7.2 Divisibility, Primes, and the Euclidean Algorithm 7.3 Modular Arithmetic, Chinese Remainder Theorem, and Euler's Totient

8 Chapter 8: Linear Algebra: Vector Spaces & Transformations

8.1 Vector Spaces, Subspaces, Span, and Linear Independence 8.2 Basis, Dimension, and Coordinate Representations 8.3 Linear Transformations, Kernel, Range, and the Rank-Nullity Theorem 8.4 Matrix Representations of Transformations and Change of Basis

9 Chapter 9: Linear Algebra: Matrices, Determinants & Spectral Theory

9.1 Systems of Linear Equations, Matrix Rank, and Row Reduction 9.2 Determinants, Matrix Inverses, and Cramer's Rule 9.3 Eigenvalues, Eigenvectors, and Diagonalization 9.4 Inner Product Spaces, Gram-Schmidt, and the Spectral Theorem

10 Chapter 10: Abstract Algebra: Groups, Rings & Fields

10.1 Groups, Subgroups, and Permutations 10.2 Cosets, Lagrange's Theorem, Normal Subgroups, and Homomorphisms 10.3 Rings, Ideals, Modules, Polynomial Rings, and Fields

11 Chapter 11: Introductory Real Analysis

11.1 The Real Field and Metric Space Topology 11.2 Compactness, Completeness, and Connectedness in R^n 11.3 Continuity, Uniform Continuity, and Value Theorems 11.4 Sequences and Series of Functions: Pointwise and Uniform Convergence

12 Chapter 12: Complex Analysis

12.1 Complex Numbers and Analytic Functions 12.2 Contour Integration and Cauchy's Theorems 12.3 Laurent Series, Singularities, and the Residue Theorem

13 Chapter 13: Topology, Geometry & Numerical Analysis

13.1 Topological Spaces, Open/Closed Sets, and Bases 13.2 Euclidean Geometry, Similarity, Circles, and Transformations 13.3 Numerical Analysis: Error, Root Finding, Interpolation, and Quadrature

14 Chapter 14: Probability, Statistics & Discrete Mathematics

14.1 Logic, Set Theory, Algorithms, and Combinatorics 14.2 Graph Theory: Trees, Cycles, Paths, and Planarity 14.3 Probability Spaces, Conditional Probability, and Bayes' Theorem 14.4 Random Variables, Expected Value, Variance, and Common Distributions

14.2 Graph Theory: Trees, Cycles, Paths, and Planarity

Key Takeaways Explain This Topic AI

The Handshaking Lemma states that sum_{v in V} deg(v) = 2|E|, which directly implies that every finite undirected graph possesses an even number of vertices of odd degree.

A graph is bipartite if and only if it contains no odd cycles; complete bipartite graphs K_{m,n} have |V| = m+n and |E| = mn with chromatic number chi(G) = 2.

Trees are minimally connected and maximally acyclic graphs satisfying |E| = |V| - 1; Cayley's formula establishes that there are n^{n-2} distinct labeled trees on n vertices.

A connected graph admits an Eulerian circuit if and only if every vertex has even degree, whereas an Eulerian trail exists if and only if exactly zero or two vertices have odd degree.

Planar graphs obey Euler's formula V - E + F = 2, yielding the edge bound E <= 3V - 6 for V >= 3 (and E <= 2V - 4 for triangle-free planar graphs); Kuratowski's theorem characterizes planarity by the absence of subgraphs homeomorphic to K_5 or K_{3,3}.

Last updated: September 2026

14.2 Graph Theory: Trees, Cycles, Paths, and Planarity

Graph theory on the GRE Mathematics Subject Test evaluates vertex degrees, connectivity, Eulerian and Hamiltonian conditions, tree invariants, and planar graph embeddings. Fluency with Euler's formula, the Handshaking Lemma, and topological criteria is essential for solving discrete mathematics problems accurately.

Simple Graphs and the Handshaking Lemma

A simple graph G = ( V , E ) G = (V, E) G = ( V , E ) has vertices V V V and undirected edges E ⊆ ( V 2 ) E \subseteq \binom{V}{2} E ⊆ ( 2 V ​ ) without loops or parallel edges. The degree deg ⁡ ( v ) \deg(v) de g ( v ) is the number of edges incident to v v v .

Handshaking Lemma

For any finite undirected graph G = ( V , E ) G = (V, E) G = ( V , E ) : ∑ v ∈ V deg ⁡ ( v ) = 2 ∣ E ∣ \sum_{v \in V} \deg(v) = 2|E| v ∈ V ∑ ​ de g ( v ) = 2∣ E ∣

Because the sum of vertex degrees is even, every graph contains an even number of vertices of odd degree.

Degree Sequences and Havel-Hakimi Theorem

A non-increasing sequence d 1 ≥ d 2 ≥ ⋯ ≥ d n d_1 \ge d_2 \ge \dots \ge d_n d 1 ​ ≥ d 2 ​ ≥ ⋯ ≥ d n ​ of non-negative integers is graphic if it is the degree sequence of a simple graph. The Havel-Hakimi theorem states that d 1 , … , d n d_1, \dots, d_n d 1 ​ , … , d n ​ is graphic if and only if the sequence formed by deleting d 1 d_1 d 1 ​ and subtracting 1 from the next d 1 d_1 d 1 ​ terms is graphic.

Bipartite Graphs and Odd Cycles

A graph G G G is bipartite if V = V 1 ∪ V 2 V = V_1 \cup V_2 V = V 1 ​ ∪ V 2 ​ with V 1 ∩ V 2 = ∅ V_1 \cap V_2 = \emptyset V 1 ​ ∩ V 2 ​ = ∅ such that every edge joins V 1 V_1 V 1 ​ and V 2 V_2 V 2 ​ .

Odd-cycle characterization: A graph G G G is bipartite if and only if G G G contains no odd cycles.

Chromatic Number: Every bipartite graph with ∣ E ∣ ≥ 1 |E| \ge 1 ∣ E ∣ ≥ 1 has chromatic number χ ( G ) = 2 \chi(G) = 2 χ ( G ) = 2 .

Complete Bipartite Graph K m , n K_{m, n} K m , n ​ : Has ∣ V ∣ = m + n |V| = m + n ∣ V ∣ = m + n , ∣ E ∣ = m n |E| = mn ∣ E ∣ = mn , and is Hamiltonian if and only if m = n ≥ 2 m = n \ge 2 m = n ≥ 2 .

Trees and Spanning Trees

A tree T T T is an undirected graph satisfying any of these equivalent definitions:

T T T is connected and acyclic.

T T T is connected with ∣ E ∣ = ∣ V ∣ − 1 |E| = |V| - 1 ∣ E ∣ = ∣ V ∣ − 1 .

T T T is acyclic with ∣ E ∣ = ∣ V ∣ − 1 |E| = |V| - 1 ∣ E ∣ = ∣ V ∣ − 1 .

Any two vertices are connected by a unique simple path.

T T T is minimally connected (removing any edge disconnects it).

T T T is maximally acyclic (adding any edge creates a unique cycle).

Leaves and Degree Distribution

Every finite tree with ∣ V ∣ ≥ 2 |V| \ge 2 ∣ V ∣ ≥ 2 contains at least two leaves ( deg ⁡ ( v ) = 1 \deg(v) = 1 de g ( v ) = 1 ). If internal vertices have degrees d 1 , … , d k ≥ 2 d_1, \dots, d_k \ge 2 d 1 ​ , … , d k ​ ≥ 2 , the leaf count ℓ \ell ℓ satisfies ℓ = 2 + ∑ i = 1 k ( d i − 2 ) \ell = 2 + \sum_{i=1}^k (d_i - 2) ℓ = 2 + ∑ i = 1 k ​ ( d i ​ − 2 ) .

Cayley's Formula and Spanning Trees

Cayley's Formula: The number of distinct labeled trees on n n n vertices is n n − 2 n^{n-2} n n − 2 .

Matrix Tree Theorem (Kirchhoff): The number of spanning trees of G G G equals any cofactor of the Laplacian matrix L = D − A L = D - A L = D − A , where D D D is the diagonal degree matrix and A A A is the adjacency matrix.

Eulerian and Hamiltonian Graphs

  • Property Eulerian Graph Hamiltonian Graph
  • Object Visited Every edge exactly once Every vertex exactly once
  • Closed Walk Eulerian circuit Hamiltonian cycle
  • Open Walk Eulerian trail Hamiltonian path
  • Characterization Exact degree parity criterion NP-complete; sufficient conditions only
  • Euler's Criterion

Connected G G G has an Eulerian circuit ⟺ \iff ⟺ every vertex has even degree.

Connected G G G has an Eulerian trail (not a circuit) ⟺ \iff ⟺ exactly 2 vertices have odd degree.

Hamiltonian Sufficient Conditions

Dirac's Theorem: If simple G G G has n ≥ 3 n \ge 3 n ≥ 3 vertices and deg ⁡ ( v ) ≥ n / 2 \deg(v) \ge n/2 de g ( v ) ≥ n /2 for all v ∈ V v \in V v ∈ V , then G G G is Hamiltonian.

Ore's Theorem: If simple G G G has n ≥ 3 n \ge 3 n ≥ 3 vertices and deg ⁡ ( u ) + deg ⁡ ( v ) ≥ n \deg(u) + \deg(v) \ge n de g ( u ) + de g ( v ) ≥ n for every non-adjacent pair u , v u, v u , v , then G G G is Hamiltonian.

Note: Dirac and Ore conditions are sufficient but not necessary: cycle C n C_n C n ​ is Hamiltonian with all degrees 2.

Planar Graphs and Kuratowski's Theorem

A graph is planar if it can be drawn in R 2 \mathbb{R}^2 R 2 without intersecting edges. A planar embedding partitions the plane into F F F faces.

  • Euler's Formula
  • For any connected planar graph: V − E + F = 2 V - E + F = 2 V − E + F = 2

For a planar graph with k k k connected components, V − E + F = 1 + k V - E + F = 1 + k V − E + F = 1 + k .

Planarity Edge Bounds

Since each face is bounded by at least 3 edges ( 2 E ≥ 3 F 2E \ge 3F 2 E ≥ 3 F ), substituting into Euler's formula gives: E ≤ 3 V − 6 ( for V ≥ 3 ) E \le 3V - 6 \quad (\text{for } V \ge 3) E ≤ 3 V − 6 ( for V ≥ 3 )

If G G G is triangle-free (girth ≥ 4 \ge 4 ≥ 4 , including all bipartite planar graphs), then 2 E ≥ 4 F 2E \ge 4F 2 E ≥ 4 F , yielding: E ≤ 2 V − 4 ( for V ≥ 4 ) E \le 2V - 4 \quad (\text{for } V \ge 4) E ≤ 2 V − 4 ( for V ≥ 4 )

Non-Planar Prototypes and Kuratowski's Theorem

K 5 K_5 K 5 ​ is non-planar: V = 5 , E = 10 > 3 ( 5 ) − 6 = 9 V = 5, E = 10 > 3(5) - 6 = 9 V = 5 , E = 10 > 3 ( 5 ) − 6 = 9 .

K 3 , 3 K_{3,3} K 3 , 3 ​ is non-planar: Bipartite ( V = 6 , E = 9 > 2 ( 6 ) − 4 = 8 V = 6, E = 9 > 2(6) - 4 = 8 V = 6 , E = 9 > 2 ( 6 ) − 4 = 8 ).

Kuratowski's Theorem: G G G is planar ⟺ G \iff G ⟺ G contains no subgraph homeomorphic to K 5 K_5 K 5 ​ or K 3 , 3 K_{3,3} K 3 , 3 ​ (Wagner's variant: no K 5 K_5 K 5 ​ or K 3 , 3 K_{3,3} K 3 , 3 ​ graph minor).

Four Color Theorem: Every planar graph is 4-vertex-colorable ( χ ( G ) ≤ 4 \chi(G) \le 4 χ ( G ) ≤ 4 ).

Step-by-Step Worked Problem

Problem: A connected planar graph has 10 vertices and partitions the plane into 8 faces. Can this graph be bipartite?

Solution:

Apply Euler's formula: For connected planar graphs, V − E + F = 2 V - E + F = 2 V − E + F = 2 . 10 − E + 8 = 2 ⟹ E = 16 10 - E + 8 = 2 \implies E = 16 10 − E + 8 = 2 ⟹ E = 16

Evaluate the bipartite planar bound: Bipartite graphs contain no odd cycles (girth ≥ 4 \ge 4 ≥ 4 ). Every face is bounded by at least 4 edges, so 2 E ≥ 4 F 2E \ge 4F 2 E ≥ 4 F , which implies F ≤ E / 2 F \le E/2 F ≤ E /2 .

Check maximum edge bound: E ≤ 2 V − 4 = 2 ( 10 ) − 4 = 16 E \le 2V - 4 = 2(10) - 4 = 16 E ≤ 2 V − 4 = 2 ( 10 ) − 4 = 16 The graph has E = 16 E = 16 E = 16 , which satisfies the bound with equality.

Constructive verification: The complete bipartite graph K 2 , 8 K_{2, 8} K 2 , 8 ​ has V = 10 V = 10 V = 10 vertices and E = 2 × 8 = 16 E = 2 \times 8 = 16 E = 2 × 8 = 16 edges. It is bipartite and planar.

Conclusion: Yes, such a graph can be bipartite.

GRE Exam Traps & Pitfalls

Trap 1: Confusing Eulerian Parity with Hamiltonian Conditions Eulerian circuits depend solely on local vertex degree parity (all degrees even). Hamiltonian cycles depend on global cycle structure; degree criteria (Dirac/Ore) are sufficient, never necessary.

Trap 2: Using E ≤ 3 V − 6 E \le 3V - 6 E ≤ 3 V − 6 on Bipartite Graphs The bound E ≤ 3 V − 6 E \le 3V - 6 E ≤ 3 V − 6 fails to prove non-planarity for bipartite graphs like K 3 , 3 K_{3,3} K 3 , 3 ​ ( 9 ≤ 12 9 \le 12 9 ≤ 12 holds). For triangle-free graphs, always use the tighter bound E ≤ 2 V − 4 E \le 2V - 4 E ≤ 2 V − 4 .

Trap 3: Labeled vs. Unlabeled Trees in Cayley's Formula Cayley's formula n n − 2 n^{n-2} n n − 2 counts labeled trees on n n n distinct vertices. Unlabeled non-isomorphic trees are vastly fewer and lack a simple power formula.

Trap 4: Neglecting Component Counts in Euler's Formula V − E + F = 2 V - E + F = 2 V − E + F = 2 requires connectedness. If a planar graph has k k k components, use V − E + F = 1 + k V - E + F = 1 + k V − E + F = 1 + k .

Loading diagram... Graph Invariant and Traversal Diagnostic Workflow