Graph theory terminology

Graph theory terminology

Edexcel International A Level Maths: Revision notes

Studying this course? Keep your progress in one place.

Key facts

  • A graph is vertices joined by edges; a digraph has directed edges; a weighted graph has numbers on its edges.
  • The degree of a vertex is the number of edges meeting at it, and the degrees always add up to twice the number of edges.
  • The number of odd vertices is always even.
  • A path repeats no vertex; a cycle is a closed path; a tree is a connected graph with no cycles and n−1n-1 edges.
  • A complete graph on nn vertices has n(n−1)2\frac{n(n-1)}{2} edges; a spanning tree uses n−1n-1 of them.

Graphs and digraphs

A graph is a set of vertices joined by edges. A weighted graph puts a number on each edge, and a digraph gives each edge a direction.

A graph is a set of vertices (nodes) joined by edges (arcs).

  • A subgraph uses 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.
  • A digraph has directed edges, each with an arrow showing the one allowed direction.

Name a graph by listing its vertices and edges.

ABCDE
Graph G: vertices A to E with edges AB, AC, BC, CD, DE

What does a digraph have that a graph need not?

Degree of a vertex

The degree of a vertex is the number of edges meeting at it. The degrees of a graph always add up to twice the number of edges.

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 GG the degrees are A:2A:2, B:2B:2, C:3C:3, D:2D:2, E:1E:1, so the odd vertices are CC and EE.

Each edge contributes 2 to the sum of the degrees, so that sum is always even. It follows that the number of odd vertices is always even. A graph with exactly three odd vertices cannot exist.

ABCDE
Graph G: degrees A 2, B 2, C 3, D 2, E 1. The odd vertices are C and E.

Degree

A:
2
B:
2
C:
3
D:
2
E:
1

Odd or even

A:
Even
B:
Even
C:
Odd
D:
Even
E:
Odd
Degrees in graph G (total 10 = 2 × 5 edges)
  • Sum of the degrees2 × number of edges

A graph has degrees 3, 3, 2, 2, 1, 1. How many edges does it have?

Walks, paths and cycles

A walk is any sequence of connected edges, a path is a walk with no repeated vertex, and a cycle is a closed path.

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.

ABCDE
In G, A-B-C-E is a path; A-B-C-D-A (shaded) is a cycle. A walk may repeat vertices, such as A-B-C-B.

Walk

  • Edges joined end to start
  • Vertices may repeat

Path

  • A walk
  • No vertex repeated

Cycle

  • A closed path
  • Starts and ends at the same vertex
Walk, path and cycle

In graph GG: C→D→EC\to D\to E is a path, A→B→C→AA\to B\to C\to A is a cycle, and A→C→D→C→AA\to C\to D\to C\to A is a walk that is not a path, because CC is repeated.

Which is true of every path?

Connected graphs and trees

A tree is a connected graph with no cycles. A tree with nn vertices has exactly n−1n-1 edges.

Two vertices are connected if there is a path between them. A connected graph has every pair of vertices connected.

A tree is a connected graph with no cycles. Adding any edge to a tree creates a cycle.

In a tree with 8 vertices the degrees sum to 2×7=142\times7=14, so at least one vertex has degree 1.

12345678
A tree with 8 vertices has 7 edges and no cycles.
  • Tree on nn verticesn−1n-1 edges, no cycles

A connected graph has 7 vertices and 7 edges. Is it a tree?

Spanning trees and complete graphs

A spanning tree is a subgraph that is a tree containing every vertex. A complete graph joins every pair of vertices and has n(n−1)2\frac{n(n-1)}{2} edges.

A spanning tree of a connected graph includes every vertex and is a tree, so it has n−1n-1 edges. To form one, delete edges that lie on cycles until none remain.

A minimum spanning tree of a weighted graph has the least total weight.

In a complete graph every pair of vertices is joined by an edge, so every vertex has degree n−1n-1.

ABCD
The complete graph K₄ has 4 × 3 ÷ 2 = 6 edges. Any spanning tree of it has 3 edges.
  • Complete graph, nn verticesn(n−1)2\dfrac{n(n-1)}{2} edges
  • Spanning treen−1n-1 edges

Worked example

A complete graph has 6 vertices. How many edges must be deleted to leave a spanning tree?

How many edges does a complete graph on 5 vertices have?

Try an exam question

A graph has vertices P, Q, R, S and T and edges PQ, PR, QR, RS and ST. (a) Write down the degree of each vertex. (b) Write down a cycle in the graph. (c) Explain why the graph is not a tree.

[4 marks]

That's the notes covered.

Carry on to the next subtopic.

Try a question

What is the degree of vertex CC?

1 mark, marked against the mark scheme

Revision notes