Special graphsAQA A-Level Further Maths: Mind map

Exam questions on Special graphs

1. A simple graph $G$ has 7 vertices and 8 edges.
   Explain why $G$ cannot be a tree.2 marks
2. A graph has vertices $P$, $Q$, $R$, $S$, $T$. Its adjacency matrix, with rows and columns in the order $P,Q,R,S,T$, is $\begin{pmatrix} 0&0&0&1&1 \\ 0&0&0&1&0 \\ 0&0&0&0&1 \\ 1&1&0&0&0 \\ 1&0&1&0&0 \end{pmatrix}$.
   Show that the graph is bipartite, stating the two sets of vertices.2 marks
3. $G$ is a simple connected graph with 6 vertices. The degrees of its vertices are 4, 4, 3, 2, 2, 1.
   Show that $G$ has 8 edges and explain why $G$ is not a tree.3 marks