Roads and junctions

A map can be drawn as dots and lines. The dots are junctions and the lines are roads. Take four junctions called A, B, C and D, and five roads: A to B, B to C, C to D, D to A, and A to C.

A map as a graph: junctions $V=\{A,B,C,D\}$, roads $E=\{AB,BC,CD,DA,AC\}$, so $|V|=4$ and $|E|=5$.

$G=(V,E)$ with $V=\{A,B,C,D\}$ and $E=\{AB,BC,CD,DA,AC\}$.

Count the roads at each junction. A has three, B has two, C has three, D has two. Their sum is ten, twice the number of roads, because every road has two ends and is counted at both.

Roads at each junction: $\mathrm{deg}A=3,\mathrm{deg}B=2,\mathrm{deg}C=3,\mathrm{deg}D=2$. Their sum $3+2+3+2=10=2|E|$, since each road has two ends.

$\mathrm{deg}A=3,\mathrm{deg}B=2,\mathrm{deg}C=3,\mathrm{deg}D=2$ and $\sum \mathrm{deg}=10=2|E|$.

Can you walk along every road exactly once? Yes if and only if zero or two of the junctions have an odd number of roads, and in the case of two you must start at one of them and end at the other. Here A and C are the odd ones. So start at A: A, B, C, D, A, C. Every road once, and you end at C.

Call a walk along every road once $W$, and the number of odd junctions $k$. Then $W\iff k\in \{0,2\}$. Here $k=2$, at $A$ and $C$, so $A\to B\to C\to D\to A\to C$ works: $5$ roads, once each.

Walk $W$, odd junctions $k$: $W\iff k\in \{0,2\}$. Here $k=2$ at $A$ and $C$, and $A\to B\to C\to D\to A\to C$ ✓.

Start at B instead and you will never manage it. No odd junction gives a loop that comes back to where it began; two odd junctions give a walk from one to the other; four odd junctions give no such walk at all.

We cannot start at $B$, since $\mathrm{deg}B=2$ is even and for $k=2$ we must start at $A$ or $C$. $k=0$ gives a loop back home, and $k=4$ gives no walk.

$\mathrm{deg}B=2$, so a start at $B$ ✗. $k=0$ a loop, $k=4$ ✗.