Graph problems
Vertex degrees and the handshake lemma, whether every edge can be walked once, the shortest path by Dijkstra's algorithm and Euler's formula V − E + F = 2.
How to solve it
A graph is points (vertices) and lines between them (edges). Acquaintances, roads, bridges — all graphs. Much is told by the degrees of the vertices, the number of edges at each: they add up to twice the number of edges, and there is always an even number of odd degrees.
Step by step
- Degrees: their sum is $2E$, so it must be even. If it is odd, no such graph exists.
- Walking every edge once (an Euler path): the graph is connected and has $0$ odd vertices (you can return to the start) or $2$ (a path from one odd vertex to the other). Otherwise it is impossible.
- The shortest path (Dijkstra): mark vertices one by one — each time the unmarked one closest to the start — and update the distances to its neighbours.
- A connected planar graph: $V - E + F = 2$, counting the outer face too.
Common mistakes
- Thinking the degrees add up to the number of edges. It is twice that — each edge counts at both ends.
- Checking the degrees for an Euler path but forgetting connectivity.
- Marking a vertex in Dijkstra's algorithm before it is the closest, and missing a shorter detour.
- Not counting the outer face in Euler's formula.