Recipe

Apply the handshaking theorem

Use when: you're given some vertex degrees, or an edge count, of a graph and asked to verify a total or find one missing degree

Goal: either a confirmed match between the degree sum and 2|E|, or the one missing degree that makes it match

Taught in The handshaking theorem

1. 1

   List the vertex degrees given directly, or compute them from an edge list by counting edges incident to each vertex.

   Example

   A graph on vertices A,B,C,D,E with edges \{A,B\},\{A,C\},\{A,D\},\{B,C\},\{B,E\},\{C,E\} has \deg(A)=3, \deg(B)=3, \deg(C)=3, \deg(D)=1, \deg(E)=2.

   Why: the theorem relates a total over every vertex, so every known degree has to be gathered before that total means anything.

2. 2

   Sum whatever degrees are known, and note whether every vertex's degree is already accounted for or exactly one is still missing.

   Example

   The graph above has 6 edges, and its five known degrees sum to 3+3+3+1+2=12.

   • every vertex's degree is known — continue on to check the sum equals 2|E|.
   • exactly one degree is unknown — continue on to solve for it.

   Why: the theorem's whole content is a single equation, so separating what's known from what's missing is what makes that equation usable.

3. 3

   Use \sum_v \deg(v)=2|E| directly, either to confirm the known sum matches, or to solve for the one missing degree.

   Example

   2(6)=12, matching the sum from the previous step exactly, so every degree above is confirmed correct.

   • verifying — check the computed sum equals 2 times the edge count exactly.
   • solving for a missing degree — compute 2|E| minus the sum of the known degrees.

   Why: every edge contributes exactly 2 to the total, one for each of its two endpoints, so the total always equals 2|E|.