Graphs, Degrees and the Handshake Lemma

A graph is simply a bunch of dots (vertices) with lines (edges) between some of them, showing which things are connected. It's not the kind of graph you plot $y = x^2$ on; the name comes from the "graphic" picture of dots and lines that chemists used for molecules. Graphs are good for anything made of connections: people and friendships, cities and roads, web pages and links, atoms and bonds. The formula $\sum \deg(v) = 2|E|$ looks fancy, but it's just three pieces: $\deg(v)$ (how many lines touch dot $v$), $\sum$ (add that up over every dot) and $2|E|$ (twice the number of lines). It says that adding up the line-ends gives you twice the number of lines, which, once you see it, is hard to argue with.

A simple graph has no loops (edges from a vertex back to itself) and at most one edge between any two vertices. A directed graph gives each edge a direction, like one-way streets or "follows" on social media.

Handshake lemma. Picture a party where some pairs shake hands. Each handshake is an edge, and each person's degree is how many hands they shook. Now ask everyone for their count and add them up. Every handshake gets reported twice, once by each person in it, so the total is exactly $2|E|$, twice the number of handshakes.

That has a surprising consequence: the number of odd-degree vertices is always even. Think about why. The total is even. The even degrees add up to something even, so the odd degrees have to add up to something even too, and a sum of odd numbers is even only when there's an even number of them. So at any party, the number of people who shook an odd number of hands is even.

A common mistake. It's tempting to think the degree sum equals the number of edges, since each edge "touches" the graph once. It doesn't: each edge touches two vertices and gets counted at both. Forgetting to divide by 2 is the classic error in handshake problems.

Special graphs.

• The complete graph $K_n$ joins every pair of $n$ vertices. An edge is just a choice of 2 vertices, so there are $\binom{n}{2} = \frac{n(n-1)}{2}$ edges, and each vertex has degree $n - 1$, one edge to each of the others.
• The cycle $C_n$ is a ring: every degree is 2.
• A bipartite graph splits its vertices into two sides with edges only between them; $K_{m,n}$ includes every such edge.

Computers store graphs as adjacency lists (each vertex's neighbors) or an adjacency matrix (a 1 in row $i$, column $j$ when $i$ and $j$ are joined).

Social networks, road maps, the web and molecules are all stored and analyzed as graphs, and degree counts are the first statistic anyone computes on them.