Named Theorems

Question 1

Konig Bipartite

Answer 1

A graph is bipartite IFF it has no odd cycles

Question 2

Mantel’s Theorem

Answer 2

Max edges on a triangle free graph is n^2/4 rounded down

Question 3

Havel-Hakimi Algorithm

Answer 3

Remove largest int x, then reduce x largest ints by 1. If new sequence is graphic so is old

Question 4

Cayley’s Theorem

**𝜏(K_n)

Answer 4

𝜏(K_n) = n ^ n-2

Question 5

Matrix-Tree Theorem

Answer 5

Suppose G is loopless, A is adjaceny matrix and D is diagonal matrix with degrees of vertices. 𝜏(G) is the determinant of A-D.

Question 6

Kruskal’s Algortithm

Answer 6

Take cheapest edge unless it makes a cycle until you get a tree. This is a MST

Question 7

Dijkstra’s Algorithm

Answer 7

Calculates the shortest distance (in weight) from a fixed vertex to any other vertex

Question 8

Berge’s Theorem (Matchings)

Answer 8

A matching is maximum IFF G has no M-augmenting path (proof by contrapositive both ways)

Question 9

Hall’s Theorem

Answer 9

Let G be bipartite. G has a matching saturating X IFF |N(S)| ≥ |S| for all S in X.

Question 10

Konig-Egervary Theorem

Answer 10

If G is bipartite, α’(G) = β(G).

Question 11

Gallai’s Theorem

Answer 11

α’(G) + β’(G) = n(G)

Question 12

Gale–Shapley algorithm

Answer 12

1. every unmatched man proposes to the favorite woman on his list.
2. Every Woman says no to all but the highest proposer, to whom they say maybe
3. If every man is matched, terminate

BETTER FOR THE PROPOSERS

Question 13

Tutte’s 1-Factor Theorem

Answer 13

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.

Question 14

Petersen’s 1-Factor

Answer 14

Every 3 regular graph without a cut edge has a 1 factor.

Question 15

Petersen’s 2-Factor

Answer 15

Let k>0. Every (2k) regular graph has a 2 factor.

Question 16

Whitney’s (Connectivity) Theorem

Answer 16

κ(G) ≤ κ’(G) ≤ δ(G)

Question 17

Whitney’s 2-Connected Theorem (at least 3 vertices)

Answer 17

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)

Question 18

Expansion Lemma

Answer 18

If G is k connected, and we add a vertex with at least k neighbors, then it is still k-connected.

Question 19

Whitney’s Ear Decomp Theorem

Answer 19

G is 2-connected IFF G has an ear decomp. Any cycle can be used as the initial cycle.

Question 20

Menger’s Theorem

Answer 20

κ(x,y) = λ(x,y) if x,y is not an edge

Question 21

Dirac Fan Lemma

Answer 21

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.

Question 22

Szekeres-Wilf

Answer 22

x(G) ≤ 1 + max {δ(H) : H in G}

Question 23

Brooks’ Theorem

Answer 23

If G is a connected graph other than an odd cycle or complete graph then x(G) ≤ Δ(G)

Question 24

Mycielski’s Construction Myc(G)

Answer 24

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}.

Question 25

Grotzch Graph

Answer 25

Myc(C5)

Question 26

Konig edge coloring

Answer 26

If G is bipartite, x’(G) = Δ(G)

Question 27

Vizing’s Theorem

Answer 27

If G is simple, then x’(G) is either Δ(G) [class 1] or Δ(G) +1 [class 2]