Graph Theory Foundations, Handshaking Lemma & Connectivity

An undirected graph G = (V, E) consists of vertices V and edges E.

The Handshaking Lemma:

sum_{v in V} deg(v) = 2 |E|

Proof: Each edge e = (u, v) contributes exactly 1 to deg(u) and 1 to deg(v). Summing over all vertices counts every edge exactly twice.

Fundamental Corollary:

Partition vertices into even degree V_{even} and odd degree V_{odd}:

sum_{v in V_{even}} deg(v) + sum_{v in V_{odd}} deg(v) = 2 |E|.

Since the total sum and the even sum are both even integers, sum_{v in V_{odd}} deg(v) must be an even integer. The sum of odd numbers can only be even if there is an even count of odd terms.

Hence, every graph has an even number of odd-degree vertices.

A graph G is Bipartite if its vertex set V can be partitioned into two disjoint subsets V_1, V_2 such that every edge connects a vertex in V_1 to a vertex in V_2.

Theorem (König): A graph is bipartite if and only if it contains no odd-length cycles.

Connectivity Metrics:

- Vertex Connectivity (kappa(G)): Minimum vertices whose removal disconnects G.

- Edge Connectivity (kappa'(G)): Minimum edges whose removal disconnects G.

- Minimum Degree (delta(G)): Minimum vertex degree in G.

Whitney's Inequality: For any graph G:

kappa(G) <= kappa'(G) <= delta(G).