Question
a.i. In the context of graph theory, explain briefly what is meant by a circuit;
a.ii.In the context of graph theory, explain briefly what is meant by an Eulerian circuit.
b. The graph $G$ has six vertices and an Eulerian circuit. Determine whether or not its complement $G^{\prime}$ can have an Eulerian circuit.
c. Find an example of a graph $H$, with five vertices, such that $H$ and its complement $H^{\prime}$ both have an Eulerian trail but neither has an Eulerian circuit. Draw $H$ and $H^{\prime}$ as your solution.
▶️Answer/Explanation
a.i. a circuit is a walk that begins and ends at the same vertex and has no repeated edges
A1
[1 mark]
a.ii.an Eulerian circuit is a circuit that contains every edge of a graph A1
[1 mark]
b. if $G$ has an Eulerian circuit all vertices are even (are of degree 2 or 4) $\boldsymbol{A 1}$ hence, $G^{\prime}$ must have all vertices odd (of degree 1 or 3 ) $\quad \boldsymbol{R 1}$ hence, $G^{\prime}$ cannot have an Eulerian circuit $\quad \boldsymbol{R 1}$
Note: Award $\boldsymbol{A 1}$ to candidates who begin by considering a specific $G$ and $G^{\prime}$ (diagram). Award $\boldsymbol{R} \mathbf{1 R} \mathbf{1}$ to candidates who then consider a general $G$ and $G^{\prime}$.
[3 marks]
c. for example
Notes: Each graph must have 3 vertices of order 2 and 2 odd vertices. Award $\mathbf{A} 2$ if one of the graphs satisfies that and the final $\boldsymbol{A} 2$ if the other graph is its complement.
Question
Consider the following weighted graph G.
▶️Answer/Explanation
a.i. State what feature of $G$ ensures that $G$ has an Eulerian trail.
a.ii.State what feature of $G$ ensures that $G$ does not have an Eulerian circuit.
b. Write down an Eulerian trail in $G$.
c.ii.Starting and finishing at B, find a solution to the Chinese postman problem for $G$.
c.iiiCalculate the total weight of the solution..a.i. $G$ has an Eulerian trail because it has (exactly) two vertices ( $B$ and $F$ ) of odd degree
R1
[1 mark]
a.ii.G does not have an Eulerian circuit because not all vertices are of even degree $\quad \boldsymbol{R 1}$
[1 mark]
b. for example BAEBCEFCDF
A1A1
Note: Award $\boldsymbol{A 1}$ for start/finish at B/F, A1 for the middle vertices.
[2 marks]
c.ii.we require the Eulerian trail in $(b),($ weight $=65) \quad($ M1)
and the minimum walk FEB (15) A1
for example BAEBCEFCDFEB A1
Note: Accept EB added to the end or FE added to the start of their answer in (b) in particular for follow through.
[3 marks]
c.iiitotal weight is $(65+15=) 80 \quad \boldsymbol{A 1}$
[1 mark]
Question
Christine and her friends live in Winnipeg, Canada. The weighted graph shows the location of their houses and the time, in minutes, to travel between each house.
Christine’s house is located at vertex $\mathrm{C}$.
a.i. Use Dijkstra’s algorithm to find the shortest time to travel from $\mathrm{C}$ to $\mathrm{F}$, clearly showing how the algorithm has been applied.
a.i.Hence write down the shortest path from $\mathrm{C}$ to $\mathrm{F}$.
b. A new road is constructed that allows Christine to travel from $\mathrm{H}$ to $\mathrm{A}$ in $t$ minutes. If Christine starts from home and uses this new road her minimum travel time to $\mathrm{A}$ is reduced, but her minimum travel time to $\mathrm{F}$ remains the same.
Find the possible values of $t$.
▶️Answer/Explanation
a.i. attempts to construct a graph or table to represent Dijkstra’s algorithm a.i. attempts to construct a graph or table to represent Dijkstra’s algorithm
EITHER
OR
a clear attempt at Step 1 (C,D, H and B considered) M1
Steps 2 and 3 correctly completed
A1
Step 4 (A : $44 \rightarrow 36$ ) correctly completed
A1
Steps 5 and 6 ( $\mathrm{E}: 41 \rightarrow 40$ and $\mathrm{F}: 58 \rightarrow 57$ or $57 \rightarrow 55$ or $58 \rightarrow 55$ ) correctly completed
A1
shortest time $=55$ (mins)
A1
[6 marks]
a.ii.CHGEF
A1
Note: Award $\boldsymbol{A 1}$ only if it is clear that Dijkstra’s algorithm has been attempted in part (a) (i). This $\boldsymbol{A 1}$ can be awarded if the candidate attempts to use Dijkstra’s algorithm but neglects to state 55 (mins).
[1 mark]
b. minimum travel time from $\mathrm{C}$ to $\mathrm{A}$ is reduced
CHA is now $12+t$ (mins)
(M1)
CBA is still $25+11$ (mins)
so $12+t<36(t<24)$
(A1)
Note: Condone $t \leq 24$.
travel time from $\mathrm{C}$ to $\mathrm{F}$ remains the same ( $55 \mathrm{mins})$
CHAF is now $12+t+21$ (mins)
(M1)
$12+t+21 \geq 55(t \geq 22)$
(A1)
so $22 \leq t<24$
A1
Note: Accept $t=22,23$.
[5 marks]