Special graphsAQA A-Level Further Maths: Flashcards

What these 13 flashcards ask

What is a simple graph?
State the handshaking lemma.
What is a tree?
How many edges does a tree on n vertices have?
How many edges does Kn have?
What is the degree of every vertex of Kn?
What is a bipartite graph?
How many edges does K{m,n} have?
Why does a triangle make a graph non-bipartite?
Define the complement G' of a simple graph G.
Degree of v in the complement?
What does a row sum of a simple graph's adjacency matrix give?
Properties of the adjacency matrix of a simple graph?

Exam questions on Special graphs

A simple graph $G$ has 7 vertices and 8 edges.
Explain why $G$ cannot be a tree.2 marks
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
$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

Written by the Exaim team, led by Shaun Daswani (Head of Upper Secondary, Improve ME Institute; MSc Financial Mathematics, Imperial College London; BSc, UCL) and Jason Daswani (operational lead, Improve ME Institute; LSE).