Graph Connectivity

Degree, paths, components, and the handshake lemma.

The idea

A graph is a set of vertices together with a set of edges, each edge joining an unordered pair of distinct vertices. The definition says nothing about where the vertices sit or how the edges are drawn, so two very different pictures can show the same graph; all that matters is which pairs are joined.

Two vertices joined by an edge are adjacent, and the degree of a vertex is the number of edges meeting it. A walk is a sequence of vertices in which each consecutive pair is adjacent, and a path is a walk that visits no vertex twice. A graph is connected if every pair of its vertices is joined by a path. A disconnected graph splits into connected components: maximal sets of vertices that reach one another by paths, with no edge running between two components.

Lemma (Handshake lemma).

In every graph, the degrees of the vertices sum to twice the number of edges: $\sum_{v} \deg(v) = 2|E|.$

Every edge meets exactly two vertices, so summing all the degrees counts each edge exactly twice. The identity holds for every graph, whatever its shape, and it converts a count of degrees into a count of edges and back.

Ways to work on it

• Walkthrough. Components, degree, and the handshake lemma.
• Practice. Count edges from degrees, or components.
• Hardest. The odd-degree-vertex corollary of the handshake lemma.

Not sure where to start? Take the ten-question placement test.