Language and properties of graphs

Language and properties of graphs

Spec DA1–DA2 · AQA A-Level Further Maths: Revision notes

Studying this course? Keep your progress in one place.

Key facts

  • A graph has vertices joined by edges; the degree of a vertex counts its edge-ends, and a loop adds 22.
  • The sum of the degrees is twice the number of edges, so the number of odd vertices is even.
  • A trail has no repeated edge, a path no repeated vertex, and a cycle is a closed path.
  • A connected graph is Eulerian if all degrees are even and semi-Eulerian if exactly two are odd.
  • A Hamiltonian graph has a cycle through every vertex once; there is no degree test.

The language of graphs

A graph is vertices joined by edges, and the degree of a vertex counts the edge-ends at it.

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 22. Every edge has two ends, so the sum of the degrees is twice the number of edges.

A subgraph uses some of the vertices and edges. A subdivision replaces an edge by a path through new vertices, adding 11 vertex and 11 edge each time.

ABCDE
Degrees: A 2, B 3, C 4, D 3, E 2 (sum 14 = 2 × 7 edges).

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

Walks, trails, paths, cycles

They are all routes along edges; they differ in whether edges or vertices may repeat and whether the route is closed.

A walk is a sequence of edges where each ends where the next begins. A graph is connected if there is a path between every pair of vertices.

In the graph above, B A C B D C E DB\,A\,C\,B\,D\,C\,E\,D is a trail: no edge is repeated, although vertices BB, CC and DD are visited more than once. A path repeats no vertex and a cycle is a closed path.

Walk

Edges may repeat:
Yes
Vertices may repeat:
Yes
Must be closed:
No

Trail

Edges may repeat:
No
Vertices may repeat:
Yes
Must be closed:
No

Path

Edges may repeat:
No
Vertices may repeat:
No
Must be closed:
No

Cycle

Edges may repeat:
No
Vertices may repeat:
Start only
Must be closed:
Yes

In the graph above, is A B C AA\,B\,C\,A a cycle?

Eulerian and semi-Eulerian graphs

Count the odd vertices: none means Eulerian, exactly two means semi-Eulerian, more means neither.

A connected graph is Eulerian if it has a closed trail using every edge exactly once. It is semi-Eulerian if it has a trail, not closed, using every edge exactly once; such a trail must start at one odd vertex and end at the other.

The graph above has degrees 2,3,4,3,22,3,4,3,2, so it is semi-Eulerian, with trails from BB to DD. Adding a second edge BDBD would make every degree even.

0 odd vertices

Type:
Eulerian
Trail using every edge once:
Closed, any start

2 odd vertices

Type:
Semi-Eulerian
Trail using every edge once:
Starts and ends at the odd vertices

More than 2

Type:
Neither
Trail using every edge once:
None exists

A connected graph has degrees 2,2,4,3,32,2,4,3,3. What type is it?

Hamiltonian graphs

A graph is Hamiltonian if it has a cycle through every vertex exactly once, and there is no simple degree test.

A Hamiltonian graph has a Hamiltonian cycle.

  • To prove a graph is Hamiltonian, write down a Hamiltonian cycle.
  • To show it is not, give a reason: a vertex of degree 11 cannot lie on a cycle, because a cycle needs two edges at each vertex.

A graph can be Eulerian but not Hamiltonian, or the reverse. In the figure the cycle P Q R S T U PP\,Q\,R\,S\,T\,U\,P is Hamiltonian, but four vertices are odd, so it is not Eulerian.

PQRSTU
Edges PQ, QR, RS, ST, TU, UP, PS and QT. The outer cycle visits every vertex once.

A graph has a vertex of degree 11. Can it be Hamiltonian?

Try an exam question

A connected graph has five vertices with degrees 22, 33, 33, 44 and 44. 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

Write down the degree of vertex CC.

1 mark, marked against the mark scheme

Revision notes