Graph theory terminologyEdexcel International A Level Maths: Revision notes

A graph is a set of vertices (nodes) joined by edges (arcs). A subgraph is a graph made from some of the vertices and edges of another graph. A weighted graph (network) has a number, such as a distance or cost, on each edge. In a digraph each edge is a directed edge, with an arrow showing the one allowed direction of travel. Graphs are named by listing the vertices and edges, e.g. vertices $A$ to $E$ with edges $AB$, $AC$, $BC$, $CD$, $DE$.

The degree (valency) of a vertex is the number of edges meeting at it. A vertex is odd or even according to its degree. In $G$ with edges $AB$, $AC$, $BC$, $CD$, $DE$ the degrees are $A:2$, $B:2$, $C:3$, $D:2$, $E:1$, so the odd vertices are $C$ and $E$. Each edge contributes 2 to the sum of the degrees, so the sum of the degrees is $2\times$ (number of edges) and is always even. It follows that the number of odd vertices is always even. A graph with exactly three odd vertices cannot exist.

A walk is a finite sequence of edges in which the end vertex of one edge is the start vertex of the next. A path is a walk in which no vertex is repeated. A cycle (circuit) is a closed path: it starts and ends at the same vertex, and no other vertex is repeated. Example in $G$: $C\to D\to E$ is a path, $A\to B\to C\to A$ is a cycle, and $A\to C\to D\to C\to A$ is a walk that is not a path, because $C$ is repeated.

Two vertices are connected if there is a path between them. A graph is a connected graph if every pair of vertices is connected. A tree is a connected graph with no cycles. A tree with $n$ vertices has exactly $n-1$ edges, and adding any edge to a tree creates a cycle. In a tree with 8 vertices the degrees sum to $2\times7=14$, so at least one vertex has degree 1.

A spanning tree of a connected graph is a subgraph that includes every vertex and is a tree, so it has $n-1$ edges. To form one, delete edges that lie on cycles until no cycle remains. A minimum spanning tree (minimum connector) of a weighted graph is a spanning tree of least total weight. In a complete graph every pair of vertices is joined by an edge. With $n$ vertices it has $\frac{n(n-1)}{2}$ edges and every vertex has degree $n-1$. For $n=6$: 15 edges and degree 5, so a spanning tree has 5 edges and 10 edges are deleted.

Use the exact terms: path, cycle, walk, tree. Give vertex lists in order (for example $P\to Q\to R\to Q\to T\to U$) and check each consecutive pair is an edge. When you apply an algorithm on a graph, show clearly each step you take. Back up statements such as "not a tree" with a reason: a named cycle, or an edge count that does not equal $n-1$.