Graph theory basics

Degrees, the handshaking lemma, connectedness, trees and Euler paths. About 8 minutes, University.

What you will do

1. Dots and lines. A graph is vertices joined by edges. The degree of a vertex is how many edges touch it.
2. Handshaking. Each edge has two ends, so the degrees add up to twice the number of edges.
3. Complete graphs. K_n joins every pair of vertices, so it has n(n-1)2 edges.
4. Trees. A tree is connected with no cycles: it has exactly one fewer edge than vertices.
5. Tracing without lifting your pen. An Euler circuit needs a connected graph with every degree even. An Euler path needs exactly two odd vertices.