Graph Theory

Köning's Theorem

A graph G is bipartite if and only if τ(G)=μ(G), where τ(G) is the size of the minimum vertex cover and μ(G) is the size of the maximum matching.

Hall's Theorem

In a bipartite graph G with bipartition (A,B), a matching covers every vertex in A if ∣N(S)∣≥∣S∣ for every subset S⊆V.

Tutte's Theorem

A graph G has a perfect matching if for every subset S⊆V(G), q(G−S)≤∣S∣ holds, where q(H) is the number of odd components in H.

Tutte's Lemma

Every 3-connected graph G, distinct from K^4, has an edge e such that contracting e keeps G 3-connected.

Petersen's Theorem

Every 3-regular (cubic) bridgeless graph has a perfect matching.

Menger’s Theorem

The minimum number of vertices whose separating A from B equals the maximum number of pairwise disjoint A-B paths in G.

Global Version of Menger's Theorem

A graph is k-connected if it contains k independent paths between any two vertices.

Kuratowski and Wagner’s Theorem

A graph G is planar if it does not contain K_5 or K_{3,3} as a minor or topological minor.

Robertson & Seymour’s Theorem

For every minor-closed class C of graphs, there exists a finite set F such that G belongs to C if it contains no minor from F.

Erdős’ Theorem

For every integer k, there exists a graph H with girth g(H)>k and chromatic number χ(H)>k.

Brooks’ Theorem

For a connected graph G that is neither complete nor an odd cycle, χ(G)≤Δ(G), where Δ(G) is the maximum degree.

Johansson's Theorem

For any triangle-free graph G with maximum degree Δ(G), χ(G)≤O(Δ(G)log⁡Δ(G)).

Berge's Theorem

A graph G is perfect if χ(H)=ω(H) for every induced subgraph H of G.

Euler's formula

For planar graphs, V−E+F=2 is a fundamental result in graph theory.

Fáry's Theorem

Every planar graph has a straight-line drawing.

Schnyder's Theorem

Every planar graph G has a straight-line drawing respecting a specific vertex order.

Koebe–Andreev–Thurston Circle Packing Theorem

Every finite planar graph can be represented by a circle packing.

Thomassen's Theorem on Planar Graphs

Every planar graph is 5-list-colorable.

Four Color Theorem

If G is a planar graph, then χ(G)≤4.

Lovász's Characterization of Perfect Graphs

A graph G is perfect if α(H)⋅ω(H)≥∣V(H) for every induced subgraph H.

Weak Perfect Graph Theorem

A graph G is perfect if and only if its complement G‾ is perfect.

Strong Perfect Graph Theorem

A graph G is perfect if neither G nor G‾ contains an odd cycle of length at least 5 as an induced subgraph.

Ear Decomposition Theorem for 2-Connected Graphs

A graph G is 2-connected if it can be constructed from a cycle by adding ears.

Wernicke's Theorem

In a planar triangulation where every vertex has deg⁡(v)≥5, there exists an edge uv such that deg⁡(u)=5 and deg⁡(v)∈{5,6}.

Baker's PTAS Theorem

For every fixed ϵ>0, there exists a PTAS for the Maximum Weight Independent Set problem on planar graphs.

Lipton-Tarjan Separator Theorem

For any n-vertex planar graph G, there exists a separator whose removal divides G into two disjoint subgraphs, each with at most 2n/3 vertices.