Networks and graph theory

Tier 1

Sum of degrees $= 2 + 3 + 3 + 4 = 12$ . Number of edges $= \dfrac{12}{2} = 6$ .
A square (cycle graph $C_4$ ): four vertices arranged in a loop, each connected to its two neighbours.
$F + V = E + 2$ , so $F + 4 = 6 + 2 = 8$ , giving $F = 4$ .
Yes. All vertex degrees ( $2, 2, 4, 4$ ) are even, so an Eulerian circuit exists.
Vertices with odd degree: the vertex with degree $1$ and the vertex with degree $3$ (two odd-degree vertices). So an Eulerian path exists (but not a circuit). It must start at one odd-degree vertex and end at the other.
True. A connected graph with $n$ vertices needs at least $n - 1$ edges (a spanning tree). For $n = 5$ , at least $4$ edges.
$F + V = E + 2$ , where $F$ = number of faces (regions), $V$ = number of vertices, $E$ = number of edges. Applies to connected planar graphs.
Sum of degrees $= 2 \times 8 = 16$ .

$F + V = E + 2$ , so $5 + V = 8 + 2 = 10$ , giving $V = 5$ .
Edges: Melbourne—Sydney, Melbourne—Brisbane, Melbourne—Perth, Sydney—Brisbane. Total $= 4$ edges.
Yes. All degrees ( $2, 2, 2, 4, 4, 4$ ) are even, so an Eulerian circuit exists. The postman can walk every street exactly once and return to the starting point.
For a simple planar graph: $E \leq 3V - 6$ . Here $3 \times 6 - 6 = 12$ and $E = 10 \leq 12$ , so this test alone does not prove non-planarity. In fact, a graph with $6$ vertices and $10$ edges could be planar. (The complete graph $K_4$ has $6$ edges; $K_5$ has $10$ edges and is not planar.) Since $K_5$ is the unique simple graph on $5$ vertices with $10$ edges, but we have $6$ vertices, a graph with $6$ vertices and $10$ edges may or may not be planar depending on its structure. The inequality is necessary but not sufficient.
Three houses and three utilities: each house connects to each utility, giving $3 \times 3 = 9$ edges. This is the complete bipartite graph $K_{3,3}$ , which is not planar (by Kuratowski’s theorem).

Four vertices have odd degree ( $3$ ). Since more than $2$ vertices have odd degree, no Eulerian path (or circuit) exists. Strategy: the council could identify pairs of odd-degree vertices and add duplicate edges (roads walked twice) to make all degrees even, minimising the total extra distance. This is the Chinese Postman approach.
The handshaking lemma states $\sum \text{degrees} = 2E$ . The left side is the sum of all degrees. Suppose $k$ vertices have odd degree. Each odd degree contributes an odd number to the sum, and each even degree contributes an even number. The total must be $2E$ (even). The sum of the even degrees is even. So the sum of the odd degrees must also be even, which requires $k$ to be even. Therefore the number of odd-degree vertices is always even.
Edges: sum of degrees $= 10 \times 3 = 30$ , so $E = \dfrac{30}{2} = 15$ . Faces: $F + V = E + 2$ , so $F + 10 = 15 + 2 = 17$ , giving $F = 7$ .
An Eulerian path visits every edge exactly once. A Hamiltonian path visits every vertex exactly once. Example: consider a graph shaped like a “bowtie” (two triangles sharing a single vertex). It has $5$ vertices and $6$ edges. The central vertex has degree $4$ and all others have degree $2$ — all even, so an Eulerian circuit exists. However, no Hamiltonian circuit exists because the graph is not $2$ -connected (removing the central vertex disconnects it).

$K_5$ : each vertex connects to $4$ others, so each has degree $4$ . Number of edges $= \dbinom{5}{2} = 10$ . All degrees are even ( $4$ ), so an Eulerian circuit exists.
Base case: $V = 1$ , edges $= 0 = 1 - 1$ . Inductive step: a tree with $V > 1$ vertices has at least one leaf (vertex of degree $1$ ). Remove the leaf and its edge: the remaining graph is a connected tree with $V - 1$ vertices and (by hypothesis) $V - 2$ edges. Adding the leaf back gives $V - 1$ edges. So a tree on $V$ vertices has $V - 1$ edges.
The vertex degrees are $3, 3, 3, 5$ — all four are odd. Since there are $4$ odd-degree vertices (more than $2$ ), no Eulerian path or circuit exists. It is impossible to cross each bridge exactly once.
Model locations as vertices and distances as weighted edges. An efficient route visiting all locations and returning to the start is a Hamiltonian circuit. You can try nearest-neighbour or other heuristics. Finding the absolute shortest Hamiltonian circuit (the Travelling Salesman Problem) is computationally difficult because the number of possible routes grows factorially: for $n$ locations there are $\dfrac{(n-1)!}{2}$ distinct routes. For large $n$ , checking all routes is impractical, so heuristic or approximation methods are used.