Graph terminology including vertices, edges, degree, paths and cycles, special graphs such as trees and complete graphs, the adjacency matrix representation, and Eulerian and Hamiltonian graphs.

What this dot point is asking

AQA wants you to use the language of graphs correctly, classify special graphs such as trees, complete and bipartite graphs, represent a graph by an adjacency matrix, calculate the degree of vertices, and recognise Eulerian and Hamiltonian graphs and the conditions for them.

Terminology

A walk is any sequence of edges; a trail is a walk with no repeated edge; a path is a trail with no repeated vertex. A cycle is a closed path that returns to its start. The degree (or valency) of a vertex counts the edges meeting it, with a loop counting twice. A graph is connected if there is a path between every pair of vertices, and a subgraph is any graph formed from a subset of the vertices and edges. A network is simply a graph whose edges carry weights, such as distances or costs, which is the form used in the algorithm questions.

A directed graph (digraph) gives each edge an orientation, so the degree splits into an in-degree and an out-degree. A simple graph has no loops and no repeated (multiple) edges between the same pair of vertices, which is the default unless a question states otherwise.

Special graphs

A tree is a connected graph with no cycles; a tree with $n$ vertices has exactly $n - 1$ edges. A complete graph $K_n$ has every pair of vertices joined, giving $\frac{n(n-1)}{2}$ edges. A bipartite graph splits its vertices into two sets with edges only between the sets.

The adjacency matrix

Eulerian and Hamiltonian graphs

A Hamiltonian graph contains a cycle visiting every vertex exactly once. Unlike the Eulerian case there is no simple degree test, which is why deciding whether a Hamiltonian cycle exists is a genuinely hard problem and underlies the travelling salesperson work.

The adjacency matrix is also a computational tool, not just a record: raising it to the power $k$ gives a matrix whose $(i, j)$ entry counts the walks of length $k$ from vertex $i$ to vertex $j$, which is how you can verify connectivity or count routes. For a complete graph $K_n$ the adjacency matrix is all ones off the diagonal, and the handshaking lemma confirms its edge count, since each of the $n$ vertices has degree $n - 1$, giving a degree sum of $n(n-1)$ and therefore $\frac{n(n-1)}{2}$ edges.

Counting and the handshaking lemma in problems

The handshaking lemma is the workhorse of the short answer questions, because it pins down an unknown degree or edge count from partial information. The most common exam move is to write the degree sum as $2E$, substitute the known degrees, and solve for the missing one. A second standard deduction is that the number of odd-degree vertices must be even: this follows because the odd degrees must combine with the even ones to give an even total, so an odd count of odd vertices is impossible. Examiners use this to ask whether a proposed list of degrees is achievable at all.

For a bipartite graph with parts of size $r$ and $s$, the complete bipartite graph $K_{r,s}$ has $rs$ edges, since every vertex in one part joins every vertex in the other. Bipartite graphs are exactly the graphs with no odd cycle, which is why a graph can be tested for bipartiteness by trying to two-colour its vertices so that no edge joins two vertices of the same colour. If a conflict appears, an odd cycle exists and the graph is not bipartite. This two-colouring idea links directly to the matching and allocation problems that build on the same topic.

Planarity and isomorphism

Two graphs are isomorphic if there is a relabelling of vertices that turns one into the other, preserving which pairs are joined. Because an adjacency matrix depends on the labelling, two isomorphic graphs can have different adjacency matrices, so a quick test for non-isomorphism is to compare invariants that do not depend on labelling: the number of vertices, the number of edges, and the sorted list of degrees. If any of these differ, the graphs cannot be isomorphic, though matching invariants do not by themselves prove isomorphism. A graph is planar if it can be drawn with no edges crossing; $K_5$ and $K_{3,3}$ are the two smallest non-planar graphs, and recognising them inside a larger graph is the usual way planarity is examined.