Graph types and Eulerian graphs

Graph types and Eulerian graphs

Spec 1.3 · Edexcel A-Level Further Maths: Revision notes

Studying this course? Keep your progress in one place.

Key facts

  • The sum of the degrees is twice the number of edges, so the number of odd vertices is even.
  • A tree is connected with no cycles; nn vertices give n−1n-1 edges.
  • KnK_n has n(n−1)2\frac{n(n-1)}{2} edges; K4K_4 is planar, K5K_5 is not.
  • Isomorphic graphs need a matching of vertices that preserves every edge.
  • Connected graph: no odd vertices is Eulerian; exactly two is semi-Eulerian; more than two is neither.

Vocabulary of graphs

A graph has vertices joined by edges; the order of a vertex is the number of edges meeting at it.

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 graph is connected if there is a path between every pair of vertices. A subgraph uses some of the vertices and edges. Every edge has two ends, so the sum of the degrees is twice the number of edges: the number of odd vertices is always even. If given edges, find every degree first and check they add up.

Path

  • Edges in sequence
  • No vertex visited twice

Cycle

  • A closed path
  • Starts and ends at the same vertex

Tree

  • Connected, no cycles
  • nn vertices, n−1n-1 edges

Spanning tree

  • A subgraph that is a tree
  • Includes every vertex

A graph has 77 edges. What is the sum of the degrees of its vertices?

Weighted graphs and digraphs

Weights label edges, digraphs give edges a direction, and a simple graph has no loops or repeated edges.

A weighted graph (network) has a number, a weight, on each edge, such as a distance, time or cost. A digraph has edges with a direction, shown by arrows, so travel is allowed only that way.

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.

Weighted graph

  • A number (weight)
  • Distances between towns

Digraph

  • A direction
  • One-way streets

Simple graph

  • No loops, no repeated edges
  • Most graphs in this topic

Which graph shows one-way streets?

Complete graphs

Every pair of vertices is joined once, so KnK_n has n(n−1)2\frac{n(n-1)}{2} edges.

A complete graph KnK_n has nn vertices with every pair joined by exactly one edge. Each vertex has degree n−1n-1, so KnK_n has n(n−1)2\frac{n(n-1)}{2} edges. For example K4K_4 has 66 edges and K5K_5 has 1010 edges.

ABCDE
The complete graph K₅: 10 edges, degree 4 at every vertex.
  • Edges of KnK_nn(n−1)2\dfrac{n(n-1)}{2}
  • Degree of each vertexn−1n-1

Worked example

KnK_n has 4545 edges. Find nn.

How many edges does K6K_6 have?

Planar and isomorphic graphs

Planar graphs can be drawn without crossings; isomorphic graphs have a vertex matching that preserves every edge.

A graph is planar if it can be drawn in a plane with no edges crossing. Edges may be bent, so a tangled-looking graph may still be planar. K4K_4 is planar, but K5K_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, edges and degrees. To prove isomorphism, state the matching and check every edge. To disprove it, find a property that differs, such as the degree sequence.

ABCD
K₄ drawn with no crossings, so K₄ is planar.

Two graphs both have 55 vertices and 66 edges, but one has a vertex of degree 44 and the other does not. Are they isomorphic?

Eulerian graphs

Count the odd vertices of a connected graph: none gives Eulerian, two gives semi-Eulerian, more gives neither.

An Eulerian cycle is a closed route that uses every edge exactly once and returns to its start. A connected graph with one is Eulerian. A graph is semi-Eulerian if it has a trail using every edge once but starting and ending at different vertices, which must be the two odd vertices.

Check the graph is connected first. Adding an edge between two odd vertices makes both even.

0 odd vertices

  • Eulerian

2 odd vertices

  • Semi-Eulerian
  • Start and end at the odd vertices

More than 2 odd vertices

  • Neither

Worked example

A connected graph has degrees 2,3,4,3,22,3,4,3,2. Is it Eulerian, semi-Eulerian or neither?

A connected graph has degrees 4,4,3,3,3,34, 4, 3, 3, 3, 3. What is it?

Try an exam question

A connected graph has six vertices with degrees 2,4,3,3,2,42,4,3,3,2,4. Find the number of edges and state, with a reason, whether the graph is Eulerian, semi-Eulerian or neither.

[4 marks]

That's the notes covered.

Carry on to the next subtopic.

Try a question

What is the sum of the degrees (orders) of the six vertices?

1 mark, marked against the mark scheme

Revision notes