Network terminology and graph representations for HSC Maths Standard 2

Sum of degrees = $2 \times$ number of edges = $2 \times 9 = 18$.

The sum of the degrees of all vertices in any graph equals twice the number of edges, because every edge contributes $1$ to each of its two endpoints. So the sum is always even.

Markers reward the formula, the calculation, and the explanation that each edge is counted twice.

For each vertex, count edges pointing in (in-degree) and edges pointing out (out-degree). List the vertices for which in-degree exceeds out-degree.

Markers reward correct counting of in and out degrees for each vertex, identification of the vertices satisfying the condition, and clear notation distinguishing in and out degrees. Note that the sum of in-degrees over all vertices equals the sum of out-degrees, both equal to the number of directed edges.

Find the degree of every vertex and count how many are odd.

A network can be traversed using each edge exactly once when it is connected and has either zero or exactly two vertices of odd degree. If every vertex is even, the trail can start anywhere and returns to its start (an Eulerian circuit). If exactly two vertices are odd, the trail must start at one of those odd vertices and finishes at the other (an Eulerian trail). Any other number of odd vertices means it cannot be traversed.

Markers reward counting the odd-degree vertices, stating the even-degree condition, and naming a valid starting vertex.

List the degree of each vertex

Count how many edge-ends meet at each station. $W$ sits at the end of section $WT$ only, so its degree is $1$. $T$ is on $WT$ and $TC$, so its degree is $2$. $C$ is on $TC$ and $CR$, so its degree is $2$. $R$ is on $CR$ only, so its degree is $1$.

Add the degrees

The sum is $1 + 2 + 2 + 1 = 6$.

Check with the handshake result

There are $3$ edges, and $\sum \text{degree} = 2 \times (\text{number of edges}) = 2 \times 3 = 6$. The total matches and is even, as it must be. Correct.

(a) Degree of the depot

Every one of the four roads has one end at $P$, so four edge-ends meet there. The degree of $P$ is $4$.

(b) Degree of a shop

Shop $A$ touches only the single road $PA$, so just one edge-end meets it. The degree of $A$ is $1$ (and the same is true of $B$, $C$ and $D$).

Check with the handshake result

The degrees are $4$, $1$, $1$, $1$, $1$, which sum to $8$. There are $4$ edges, and $2 \times 4 = 8$. The totals agree, so the counts are right.

(a) Find each degree

Tick off the edges at each vertex. $A$ is on $AB$ and $CA$, so its degree is $2$. $B$ is on $AB$ and $BC$, so its degree is $2$. $C$ is on $BC$, $CA$ and $CD$, so its degree is $3$. $D$ is on $CD$ only, so its degree is $1$.

(b) Count the odd-degree vertices

Odd degrees occur at $C$ (degree $3$) and $D$ (degree $1$). That is $2$ vertices of odd degree.

Check with the handshake result

The degrees sum to $2 + 2 + 3 + 1 = 8 = 2 \times 4$ for the $4$ edges, and the number of odd-degree vertices ($2$) is even, exactly as the handshake result guarantees. Correct.

(a) Use the handshake result

The sum of the degrees equals twice the number of edges: $\sum \text{degree} = 2 \times 7 = 14$.

(b) Subtract the known degrees

Four vertices contribute $4 \times 3 = 12$ to the total of $14$, so the fifth vertex has degree $14 - 12 = 2$.

Check

The degrees are $3$, $3$, $3$, $3$, $2$, which sum to $14 = 2 \times 7$. The total is even and matches twice the edge count. Correct.

(a) Test the tree definition

A tree is a connected graph with no cycles. Starting at $A$ you can reach $B$ and $C$ directly, then $D$ and $E$ from $C$, then $F$ from $E$, so all six towns are reachable and the graph is connected. There are $5$ edges on $6$ vertices, and no edge closes a loop (each town past the first is joined on by exactly one new link), so there is no cycle. The network is a tree.

(b) Apply the $n - 1$ fact

A tree on $n$ vertices has exactly $n - 1$ edges, so a tree connecting $n = 6$ towns must have $6 - 1 = 5$ links.

Check

The plan uses $5$ links for $6$ towns, which is exactly $n - 1$, consistent with it being a tree. The degrees $2 + 1 + 3 + 1 + 2 + 1 = 10 = 2 \times 5$ also pass the handshake check. Correct.

(a) Find the degrees

$A$ is on $AB$, $DA$ and $AC$, so degree $3$. $B$ is on $AB$ and $BC$, so degree $2$. $C$ is on $BC$, $CD$ and $AC$, so degree $3$. $D$ is on $CD$ and $DA$, so degree $2$.

(b) Apply the traversability rule

The graph is connected, and the odd-degree vertices are $A$ and $C$ ($2$ of them). A connected graph with exactly $2$ odd-degree vertices has an Eulerian trail but no circuit, so it can be traversed and the trail must start at one odd vertex and finish at the other. Begin at $A$ (or at $C$).

(c) Give a trail

One valid trail is $A \to B \to C \to D \to A \to C$. It uses each of the $5$ edges once and ends at $C$, the other odd vertex.

Check

Degrees sum to $3 + 2 + 3 + 2 = 10 = 2 \times 5$ for the $5$ edges; exactly $2$ vertices are odd; and the listed trail uses all $5$ edges once. Correct.

(a) Count in and out at each vertex. For each arrow, add $1$ to the out-degree of its tail and $1$ to the in-degree of its head.

• $A$: in $1$ (from $E$), out $2$ (to $B$, $C$).
• $B$: in $2$ (from $A$, $D$), out $1$ (to $C$).
• $C$: in $2$ (from $B$, $A$), out $1$ (to $D$).
• $D$: in $1$ (from $C$), out $2$ (to $B$, $E$).
• $E$: in $1$ (from $D$), out $1$ (to $A$).

(b) Compare the two columns. In-degree exceeds out-degree at $B$ ($2 > 1$) and $C$ ($2 > 1$).

Check with the directed sum rule. The in-degrees sum to $1 + 2 + 2 + 1 + 1 = 7$ and the out-degrees sum to $2 + 1 + 1 + 2 + 1 = 7$. Both equal the $7$ directed edges, so no direction was miscounted. Correct.

(a) Read each degree from the edge list

Count the edges containing each vertex. $A$: $AB$, $AE$, degree $2$. $B$: $AB$, $BC$, $BE$, degree $3$. $C$: $BC$, $CD$, degree $2$. $D$: $CD$, $DE$, degree $2$. $E$: $AE$, $BE$, $DE$, degree $3$.

(b) Apply the traversability rule

The graph is connected, and the odd-degree vertices are $B$ and $E$ (degree $3$ each), which is exactly $2$. A connected graph with $2$ odd-degree vertices has an Eulerian trail, so it can be traversed; the trail must start at one odd vertex and end at the other. Begin at $B$ (one trail is $B \to E \to D \to C \to B \to A \to E$).

Check

Degrees sum to $2 + 3 + 2 + 2 + 3 = 12 = 2 \times 6$ for the $6$ edges, and exactly $2$ vertices are odd, so the rule applies and the count is consistent. Correct.

(a) Find the degrees

$A$: $AB$, $CA$, degree $2$. $B$: $AB$, $BC$, degree $2$. $C$: $BC$, $CA$, $CD$, $EC$, degree $4$ (it is the shared vertex). $D$: $CD$, $DE$, degree $2$. $E$: $DE$, $EC$, degree $2$.

(b) Explain the Eulerian circuit

Every vertex has even degree, so the number of odd-degree vertices is $0$, and the graph is connected. A connected graph with no odd-degree vertices has an Eulerian circuit: a trail using every edge exactly once that returns to its starting vertex, and it may begin anywhere. One such circuit from $A$ is $A \to C \to E \to D \to C \to B \to A$.

Check

Degrees sum to $2 + 2 + 4 + 2 + 2 = 12 = 2 \times 6$ for the $6$ edges; there are $0$ odd-degree vertices; and the listed circuit uses all $6$ edges once and returns to $A$. Correct.

(a) Trace the components

Starting at $A$ you can reach $B$ and $C$ (edges $AB$, $AC$, $BC$) but no further, since none of $A$, $B$, $C$ joins any of $D$, $E$, $F$, $G$. Starting at $D$ you reach $E$, $F$, $G$ along $DE$, $EF$, $FG$. So the graph is disconnected, with two components $\{A, B, C\}$ and $\{D, E, F, G\}$.

(b) Apply the traversability rule

A single trail covering every edge exists only for a connected graph. Because the graph splits into two separate components, no one trail can cross from one component to the other, so the whole graph cannot be traversed using every edge exactly once. (Each component on its own is traversable, but that is two separate trails, not one.)

Check

Degrees are $A 2$, $B 2$, $C 2$, $D 1$, $E 2$, $F 2$, $G 1$, summing to $12 = 2 \times 6$ for the $6$ edges. The handshake check passes, but connectedness fails, so the no-traversal conclusion stands. Correct.

(a) Count edges and test the tree definition

There are $5$ edges joining the $6$ vertices in a single chain. The graph is connected, and a connected graph on $n$ vertices with exactly $n - 1$ edges is a tree (it has no cycle). Here $n = 6$ and $n - 1 = 5$, which matches, so the network is a tree.

(b) Find the extra edges needed

A tree has no cycle, and adding any one edge between two of its vertices creates a second path between them, which closes a cycle. So $1$ extra edge is enough, and since a tree starts with no cycle at all, at least $1$ is required. The smallest number of extra edges is therefore $1$. (For example, adding $AF$ closes the cycle $A \to B \to C \to D \to E \to F \to A$.)

Check

Before the addition, $5$ edges on $6$ vertices gives $n - 1$, confirming a tree with no cycle. After adding $1$ edge there are $6$ edges on $6$ vertices; a connected graph with $n$ vertices and $n$ or more edges must contain a cycle, so $1$ edge does guarantee one. Correct.

(a) Find the degrees

Count edges at each vertex. $A$: $AB$, $AC$, degree $2$. $B$: $AB$, $BC$, $BD$, degree $3$. $C$: $AC$, $BC$, $CE$, degree $3$. $D$: $BD$, $DE$, $DF$, degree $3$. $E$: $CE$, $DE$, $EF$, degree $3$. $F$: $DF$, $EF$, degree $2$.

(b) Verify the edge count

The degrees sum to $2 + 3 + 3 + 3 + 3 + 2 = 16$. By the handshake result $\sum \text{degree} = 2 \times (\text{number of edges})$, so the number of edges is $16 \div 2 = 8$, matching the eight roads listed.

(c) Apply the traversability rule

The odd-degree vertices are $B$, $C$, $D$, $E$, which is $4$ of them. A connected graph is traversable only when it has $0$ or $2$ odd-degree vertices, so with $4$ odd vertices this network cannot be traversed using each road exactly once.

(d) Add the weights along each path

For $A \to B \to D \to F$: $AB + BD + DF = 4 + 5 + 8 = 17$ km. For $A \to C \to E \to F$: $AC + CE + EF = 7 + 6 + 9 = 22$ km. Since $17 < 22$, the path $A \to B \to D \to F$ is shorter.

Check

Degrees sum to $16 = 2 \times 8$, so part (b) is consistent; there are $4$ odd vertices, confirming part (c); and the path lengths $17$ and $22$ each add three edge weights, with the smaller giving the shorter route. Correct.