Overview

Graph theory problems often rely on invariants such as degree sums and connectivity.

Key Ideas

• Handshaking lemma: the sum of degrees equals $2E$.
• Trees with $n$ vertices have $n-1$ edges.
• Parity arguments are common in graph proofs.

Worked Example

Show that any graph has an even number of vertices of odd degree.

The sum of degrees is $2E$, an even number. A sum of degrees is even only if the count of odd terms is even.

Practice Problems