Named Theorems Flashcards
Konig Bipartite
A graph is bipartite IFF it has no odd cycles
Mantel’s Theorem
Max edges on a triangle free graph is n^2/4 rounded down
Havel-Hakimi Algorithm
Remove largest int x, then reduce x largest ints by 1. If new sequence is graphic so is old
Cayley’s Theorem
**𝜏(K_n)
𝜏(K_n) = n ^ n-2
Matrix-Tree Theorem
Suppose G is loopless, A is adjaceny matrix and D is diagonal matrix with degrees of vertices. 𝜏(G) is the determinant of A-D.
Kruskal’s Algortithm
Take cheapest edge unless it makes a cycle until you get a tree. This is a MST
Dijkstra’s Algorithm
Calculates the shortest distance (in weight) from a fixed vertex to any other vertex
Berge’s Theorem (Matchings)
A matching is maximum IFF G has no M-augmenting path (proof by contrapositive both ways)
Hall’s Theorem
Let G be bipartite. G has a matching saturating X IFF |N(S)| ≥ |S| for all S in X.
Konig-Egervary Theorem
If G is bipartite, α’(G) = β(G).
Gallai’s Theorem
α’(G) + β’(G) = n(G)
Gale–Shapley algorithm
- every unmatched man proposes to the favorite woman on his list.
- Every Woman says no to all but the highest proposer, to whom they say maybe
- If every man is matched, terminate
BETTER FOR THE PROPOSERS
Tutte’s 1-Factor Theorem
A graph has a 1 factor IFF o(G-S) ≤ |S| for all sets of vertices S. **o(G-S) = the number of components of G-S with an odd number of vertices. If we find an S that violates, there is no 1-factor and thus no perfect matching.
Petersen’s 1-Factor
Every 3 regular graph without a cut edge has a 1 factor.
Petersen’s 2-Factor
Let k>0. Every (2k) regular graph has a 2 factor.
Whitney’s (Connectivity) Theorem
κ(G) ≤ κ’(G) ≤ δ(G)
Whitney’s 2-Connected Theorem (at least 3 vertices)
A graph on at least 3 vertices is 2-connected IFF for all u,v there are 2 internally disjoint uv paths. (pf by induction on distance of shortest uv path)
Expansion Lemma
If G is k connected, and we add a vertex with at least k neighbors, then it is still k-connected.
Whitney’s Ear Decomp Theorem
G is 2-connected IFF G has an ear decomp. Any cycle can be used as the initial cycle.
Menger’s Theorem
κ(x,y) = λ(x,y) if x,y is not an edge
Dirac Fan Lemma
Let G be a graph on at least k+1 vertices. G is k-connected IFF for every vertex and set U of at least k vertices there is an xU fan of size k.
Szekeres-Wilf
x(G) ≤ 1 + max {δ(H) : H in G}
Brooks’ Theorem
If G is a connected graph other than an odd cycle or complete graph then x(G) ≤ Δ(G)
Mycielski’s Construction Myc(G)
Graph with the vertex set {v1, v2… vn} U {u1, u2, … un}{ U {w} in which all edges vivj in G implies vivj, uivj, viuj are all edges in Myc(G) and N(w) = {u1, u2… un}.
Grotzch Graph
Myc(C5)
Konig edge coloring
If G is bipartite, x’(G) = Δ(G)
Vizing’s Theorem
If G is simple, then x’(G) is either Δ(G) [class 1] or Δ(G) +1 [class 2]