Graph types and Eulerian graphsEdexcel A-Level Further Maths: Revision notes

A graph is a set of vertices (nodes) joined by edges (arcs). The order (degree) of a vertex is the number of edges that meet at it.

• A path is a sequence of edges in which each edge starts where the last one ended and no vertex is visited twice.
• A cycle is a closed path: it starts and ends at the same vertex and visits no other vertex twice.
• A graph is connected if there is a path between every pair of vertices.
• A subgraph is formed from some of the vertices and edges of a graph.
• A tree is a connected graph with no cycles. A tree with $n$ vertices has $n-1$ edges.
• A spanning tree is a subgraph that is a tree and includes every vertex of the graph. Every edge has two ends, so the sum of the degrees of all vertices is twice the number of edges. This means the number of odd vertices is always even.

A weighted graph (network) has a number, called a weight, on each edge, for example a distance, time or cost. A digraph (directed graph) has edges with a direction, shown by arrows, so travel is allowed only in the direction given. A simple graph has no loops (edges from a vertex to itself) and no more than one edge between the same pair of vertices. The graphs in this topic are simple unless stated.

A complete graph $K_n$ has $n$ vertices with every pair of vertices joined by exactly one edge. Each vertex has degree $n-1$, so $K_n$ has $\frac{n(n-1)}{2}$ edges. For example $K_4$ has 6 edges and $K_5$ has 10 edges. Solving for $n$: if $K_n$ has 45 edges then $n^2-n-90=0$, so $n=10$.

A graph is planar if it can be drawn in a plane with no edges crossing. Edges may be bent, so a graph that looks tangled may still be planar. $K_4$ is planar, but $K_5$ is not. Two graphs are isomorphic if there is a one-to-one matching of vertices so that two vertices are joined in one graph exactly when their matches are joined in the other. They have the same number of vertices, the same number of edges and the same degrees. To prove isomorphism, state the matching and check every edge. To show graphs are not isomorphic, find a property that differs, such as the degree sequence.

An Eulerian cycle is a closed route that uses every edge exactly once and returns to its start. A graph is Eulerian if it is connected and has an Eulerian cycle. A graph is semi-Eulerian if it has a trail that uses every edge exactly once but starts and ends at different vertices. The test uses the degrees of the vertices of a connected graph:

• all vertices even: Eulerian
• exactly two vertices odd: semi-Eulerian, and the trail must start at one odd vertex and end at the other
• more than two odd vertices: neither. Example: a graph has degrees $2,3,4,3,2$. Exactly two are odd, so it is semi-Eulerian.