Language and properties of graphsAQA A-Level Further Maths: Revision notes

A graph has vertices joined by edges. A loop joins a vertex to itself, and multiple edges join the same pair of vertices more than once. A graph with neither is simple. The degree of a vertex is the number of edge-ends at it, so a loop adds $2$. Because every edge has two ends, the sum of the degrees is twice the number of edges, so the number of odd vertices is always even. A subgraph uses some of the vertices and edges of a graph. A subdivision replaces an edge by a path through new vertices, so subdividing once adds $1$ vertex and $1$ edge.

A walk is a sequence of edges where each ends where the next begins. A trail is a walk with no repeated edge. A path is a walk with no repeated vertex. A cycle is a closed path: it starts and ends at the same vertex and repeats no other vertex. A graph is connected if there is a path between every pair of vertices. Example: in the graph with edges $AB$, $AC$, $BC$, $BD$, $CD$, $CE$, $DE$, the sequence $B\,A\,C\,B\,D\,C\,E\,D$ is a trail (no edge repeated, although vertices $B$, $C$, $D$ are visited more than once).

A connected graph is Eulerian if it has a closed trail using every edge exactly once, and semi-Eulerian if it has a trail (not closed) using every edge exactly once. The tests use degrees:

• every vertex has even degree: Eulerian
• exactly two vertices have odd degree: semi-Eulerian, and every such trail must start at one odd vertex and end at the other
• more than two odd vertices: neither. Example: the graph above has degrees $2,3,4,3,2$, so it is semi-Eulerian, with trails from $B$ to $D$. Adding a second edge $BD$ would make every degree even.

A graph is Hamiltonian if it has a cycle that passes through every vertex exactly once (a Hamiltonian cycle). Unlike the Eulerian case there is no simple test using degrees, so:

• to prove a graph is Hamiltonian, write down a Hamiltonian cycle;
• to show it is not, use a reason, for example a vertex of degree $1$ cannot lie on a cycle, because a cycle needs two edges at each of its vertices. A graph can be Eulerian but not Hamiltonian, or the reverse. For a graph with edges $PQ,QR,RS,ST,TU,UP,PS,QT$, the cycle $P\,Q\,R\,S\,T\,U\,P$ is Hamiltonian, but there are four odd vertices so it is not Eulerian.