Special graphsAQA A-Level Further Maths: Revision notes

A graph is a set of vertices (nodes) joined by edges. The degree of a vertex is the number of edges meeting it. A loop joins a vertex to itself and multiple edges join the same pair of vertices more than once. A simple graph has neither loops nor multiple edges, so each pair of vertices is joined by at most one edge. A graph is connected if there is a path between every pair of vertices. Every edge has two ends, so the handshaking lemma holds: $\sum\deg(v)=2\times(\text{number of edges}).$ A simple graph with 5 vertices and degrees $3,3,2,2,2$ has $\frac{12}{2}=6$ edges.

A simple-connected graph is both simple and connected. A cycle is a closed path that starts and ends at the same vertex and repeats no other vertex. A tree is a connected graph with no cycles. For a tree with $n$ vertices:

• it has exactly $n-1$ edges;
• there is exactly one path between any two vertices;
• removing any edge disconnects it. A connected graph with $n$ vertices and $n-1$ edges is therefore a tree. A spanning tree of a connected graph uses all its vertices and enough of its edges to form a tree. A connected graph with more than $n-1$ edges must contain a cycle.

A complete graph $K_n$ is a simple graph on $n$ vertices in which every pair of vertices is joined by an edge. Each vertex has degree $n-1$, so $\text{edges}=\frac{n(n-1)}{2}.$ $K_4$ has 6 edges, $K_5$ has 10 and $K_6$ has 15. Every simple graph on $n$ vertices has at most $\frac{n(n-1)}{2}$ edges.

A bipartite graph has its vertices split into two sets so that every edge joins a vertex in one set to a vertex in the other; no edge lies within a set. In a complete bipartite graph $K_{m,n}$ the sets have $m$ and $n$ vertices and every vertex of one set is joined to every vertex of the other, so $\text{edges}=mn.$ Vertices in the $m$-set have degree $n$, and vertices in the $n$-set have degree $m$. $K_{3,2}$ has 6 edges. To test whether a graph is bipartite, colour a vertex red, its neighbours blue, their neighbours red and so on. If two adjacent vertices ever need the same colour, the graph is not bipartite. In particular a graph containing a triangle is not bipartite.

The complement $G'$ of a simple graph $G$ has the same vertices, and two vertices are adjacent in $G'$ exactly when they are not adjacent in $G$. Hence:

• $G$ and $G'$ together make up $K_n$, so $e(G)+e(G')=\frac{n(n-1)}{2}$;
• $\deg_{G'}(v)=n-1-\deg_G(v)$;
• the complement of $K_n$ has no edges. Example: if $G$ has 5 vertices and 4 edges, then $G'$ has $10-4=6$ edges.

The adjacency matrix of a graph with $n$ vertices is the $n\times n$ matrix whose entry in row $i$, column $j$ is the number of edges joining vertex $i$ to vertex $j$. For a simple graph every entry is 0 or 1, the diagonal is all 0 and the matrix is symmetric.

• Row sums give the degrees; the sum of all entries is twice the number of edges.
• $K_n$: every off-diagonal entry is 1.
• Bipartite: ordering the vertices by set gives two zero blocks on the leading diagonal, e.g. $K_{2,2}$ is $\begin{pmatrix} 0&0&1&1 \\ 0&0&1&1 \\ 1&1&0&0 \\ 1&1&0&0 \end{pmatrix}$.
• Complement: swap 0 and 1 everywhere off the diagonal, keeping the diagonal 0.