Graph theory terminologyEdexcel International A Level Maths: Mind map

Exam questions on Graph theory terminology

1. A graph $G$ has vertices $A, B, C, D, E$ and edges $AB$, $AC$, $BC$, $CD$ and $DE$.
   State, with a reason, whether $G$ is a tree.2 marks
2. $K$ is the complete graph with 6 vertices.
   A spanning tree of $K$ is formed by deleting edges. State the number of edges in the spanning tree and the number of edges deleted.2 marks
3. A graph $H$ has vertices $P, Q, R, S, T, U$ and edges $PQ$, $QR$, $RS$, $ST$, $TU$, $UP$ and $QT$.
   (i) Write down a cycle in $H$ that contains exactly four vertices. (ii) Write down a walk in $H$ of five edges that is not a path.3 marks