Graph types and Eulerian graphsEdexcel A-Level Further Maths: Mind map

Exam questions on Graph types and Eulerian graphs

1. A simple connected graph has six vertices $A$, $B$, $C$, $D$, $E$ and $F$. Its edges are $AB$, $AC$, $BC$, $BD$, $CE$, $DE$, $DF$ and $EF$.
   The edge $BE$ is added to the graph. Explain why the new graph is semi-Eulerian.2 marks
2. The complete graph $K_n$ has $n$ vertices, and every pair of distinct vertices is joined by exactly one edge.
   Given that $K_n$ has 45 edges, find the value of $n$.2 marks
3. A weighted network has five vertices $P$, $Q$, $R$, $S$ and $T$. Its edges and weights are $PQ=5$, $PR=3$, $QR=4$, $QS=6$, $RS=2$, $RT=7$ and $ST=4$.
   Explain what is meant by a spanning tree of this network, and state how many edges every spanning tree of it contains.3 marks