Recipe

Check a degree list and find the edge count

Use when: you're given a list of vertex degrees, with no picture of the graph, and asked whether it's valid, how many edges it has, or both

Goal: either a confirmed impossible list, or a valid one paired with its exact edge count

Taught in Review: graphs, degree, and the handshaking theorem

1. 1

   Sum all the numbers in the given degree list. That total will need to satisfy one exact requirement in the next step, whether or not you've ever seen the actual graph.

   Example

   For the degree list 3, 2, 2, 2, 3: 3+2+2+2+3=12.

   Why: the handshaking theorem ties this sum directly to the edge count, so nothing else about the graph's layout matters yet.

2. 2

   A valid degree list's sum must come out even, since the handshaking theorem says the sum always equals twice the edge count. An odd sum means no real graph has this degree list.

   Example

   12 is even, so 3, 2, 2, 2, 3 passes this check.

   • the sum is odd — the list is impossible, stop here
   • the sum is even — the list survives this check, continue to Step 3

   ⚡ Shortcut

   Skip adding the whole list first: count how many degrees are odd. If that count is odd, the list fails immediately, with no addition needed at all. For 3, 3, 3, 2: three entries (3, 3, 3) are odd, an odd count, so this list is impossible on sight, without ever computing 3+3+3+2=11.

   Why: an even total can only be built from an even number of odd addends, since every even-degree entry can never flip the sum's parity.

3. 3

   Divide the sum from Step 1 by 2 to get the number of edges. The handshaking theorem guarantees this comes out to a whole number whenever Step 2 passed.

   Example

   12 \div 2 = 6, so a graph with degree list 3,2,2,2,3 has exactly 6 edges.

   Why: the theorem states the degree sum equals exactly twice the edge count, so this division is the only step left once the sum is confirmed valid.