Trees
————–
Motivation : Road Repair → Given G = (V, E), repair the minimum number of roads, s.t., every city is reachable from another, and the price is minimized.

Defⁿ : A tree is a connected graph without cycles (Undirected) ≡ A tree is a connected graph with (|V| - 1) nodes and no cycles (Directed)
Defⁿ(Equivalent) : A tree is also a graph G, s.t., ∀ vᵢ,vⱼ ∈ V, ∃ a unique path p(vᵢ → vⱼ)

These statements are equivalent, and can be proved using transitivity of implications. Proofs rely on simple induction over the vertices for the first proof, and on proof by contradiction for the remaining two implications.

Minimum Spanning Tree → Given a graph G = (V, E), a MST(G) = { Tree | argmin(∑eᵢ), ∀ eᵢ ∈ E(G) }

Kruskal's Algorithm :
i) Sort Edge-List, MAKE-SET(v), ∀ v ∈ V(G) [O(|E|lg(|E|))]
ii) ∀ e = (vᵢ, vⱼ) ∈ sorted(Edge-List):
iii) if FIND-ROOT(vᵢ) ≠ FIND-ROOT(vⱼ) :
append(e), ∑eᵢ += w(e)

Kruskal's Proof of Correctness : Induction on Edges in the MST

Bipartite Graphs & Matchings
———————————————–———————————–

Motivation : Job Assignment problem → Given n job-openings, and m-people, create G = (V, E), s.t., G is Bi-Partite.

Defⁿ : G = (V, E) is Bi-Partite, if V = L ∪ R , and L ∩ R = φ, and ∀ e ∈ E, e = (vᵢ, vⱼ), where, vᵢ ∈ L and vⱼ ∈ R

Thᵐ : G = (V, E) is Bi-Partite ⇔ ∄ Odd_Cycle ⊂ G
Proof : We split into 2 cases -
a) Given : G = (V, E), s.t., G is Bi-Partite
Then, if ∃ Odd_Cycle ⊂ G, we see that a vertex v₁ and vₒ must be connected. However, as vₑ ∈ L and vₒ ∈ R, v₁vₒ is an edge in R. This is a contradiction.
b) Given : G = (V, E), s.t., ∄ Odd_Cycle ⊂ G
Then, create two sets L, R = φ . Choose some v ∈ V, and put all nodes at odd distance in R, and all nodes at even distance in L.
- If there was a path of distance even for some v' ∈ R, then, we have a cycle C = v ... v' ... v, where |C| = Even + Odd = Odd. This is a contradiction.
- If there was a path of distance odd for some v' ∈ L, then, we have a cycle C = v ... v' ... v, where |C| = Odd + Even = Odd. This is a contradiction.
QED.

Defⁿ (Matching) : A Matching M of a graph G = (V, E) is a set of edges E' ⊆ E, s.t., ∀ eᵢ = (v₀, v₁), eⱼ = (v₂, v₃), eᵢ ∩ eⱼ = φ
Maximal Matching → Cannot be extended to a larger matching.
Maximum Matching → Matching of the largest size.

Defⁿ (Neighborhood) : For a graph G = (V, E), where S ⊆ V, N(S) = ∪ M, where, M = { v' | e = (s, v') ∈ E }, ∀ s ∈ S

Thᵐ (Hall's) : In a Bi-Partite Graph (L ∪ R, E), ∃ matching M from L ⇔ ∀ S ⊆ L, |S| ≤ |N(S)|
Proof : Proof by contradiction, using the Pigeonhole Principle (Direction 1), Proof by induction on vertices (Direction 2)

Planar Graphs & Euler's Formula
——————————————————————————————–

Defⁿ : A Graph G = (V, E) is planar if it can be drawn, s.t., no 2 edges overlap.

Defⁿ (Face of a Graph) : A Face of a Graph G = (V, E) is a region bounded by edges. ∀ Graphs G = (V, E) → ∃ a Face that is infinite.

Thᵐ : Given a Connected Planar Graph G = (V, E), then, |V| - |E| + |F| = 2
Proof : Induction on the Number of Cycles in Graph.

Observations (Assuming, |V| ≥ 3):
1) ∀ f ∈ F, for some planar G = (V, E), every face has ≥ 3 edges (i.e., it is made, at the very least, by C₃)
2) ∀ e ∈ E, for some planar G = (V, E), every edge is a member of ≤ 2 faces.
3) ∀ # of pairs p = (face, edge), where, edge is in face :
a) p ≥ 3f
b) p ≤ 2e
This implies : 3f ≤ 2e => f ≤ 2e/3
So : |V| - |E| + |F| = 2 => 2 ≤ |V| -|E| + 2|E|/3 => |E| ≤ 3|V| - 6

Corollary : ∀ planar G = (V, E), ∃ v ∈ V, s.t., max(deg(v)) ≤ 5
Proof : If ∀ v ∈ V, deg(v) ≥ 6 -> ∑deg(vᵢ)/2 ≥ 6|V|/2 ≥ 3|V| = |E|
However, as |E| ≤ 3|V| - 6, this is a contradiction.
QED.