Road maps, friendships, computer networks and molecules all have the same skeleton: things, and connections between pairs of them. A graph is that skeleton. It is built from sets, and its first theorem is a counting argument in the spirit of the sum rule.
Key idea
A graph $G = (V, E)$ has a set $V$ of vertices and a set $E$ of edges, each edge joining two different vertices (on this site graphs are simple: no loops, no repeated edges, unless a problem says otherwise). The degree $\deg(v)$ of a vertex is the number of edges touching it. Handshake lemma: $$\sum_{v \in V} \deg(v) = 2|E|.$$
Why it works
Count the pairs (vertex, edge touching it) in two ways. Going vertex by vertex, there are $\deg(v)$ pairs for each $v$, so the total is the sum of the degrees. Going edge by edge, each edge touches exactly two vertices, so the total is $2|E|$. Same pairs, two counts, equal totals. A consequence: the sum of the degrees is even, so the number of vertices with odd degree must be even.
Worked examples
Worked example: Edges from degrees
A graph has degree sequence $3, 3, 2, 2, 2$. How many edges does it have?
- Sum of degrees: $3 + 3 + 2 + 2 + 2 = 12$.
- Handshake lemma: $2|E| = 12$, so $|E| = 6$.
Answer: $6$
Worked example: An impossible graph
Can a graph have degrees $3, 3, 3, 2, 2$?
- The degrees add to $13$, an odd number.
- But the sum must be $2|E|$, which is even. So no graph has these degrees.
- Equivalently: it would have three vertices of odd degree, and the number of odd-degree vertices is always even.
Answer: No
Worked example: A handshake puzzle
At a party of $9$ people, can everyone shake hands with exactly $3$ others?
- Make a graph: people are vertices, handshakes are edges. Each vertex would have degree $3$.
- The degree sum would be $9 \cdot 3 = 27$, which is odd, but it must equal twice the number of handshakes.
- So it is impossible. (With $10$ people it is possible: the sum is $30$, for $15$ handshakes.)
Answer: No
Common mistake
Believing a graph can have an odd number of odd-degree vertices. When building examples, it is easy to write down degrees like $3, 2, 2, 2$ and look for a graph. None exists: the sum $9$ is odd. Check: add the degrees first; if the total is odd, stop.
The degree sequence lists the degrees from largest to smallest. Two very different-looking drawings can have the same degree sequence; a drawing is just one picture of a graph.