Graph theory terminology
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 edges.
- A complete graph on vertices has edges; a spanning tree uses 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.
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 the degrees are , , , , , so the odd vertices are and .
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.
| Degree | Odd or even | |
|---|---|---|
| A | 2 | Even |
| B | 2 | Even |
| C | 3 | Odd |
| D | 2 | Even |
| E | 1 | Odd |
Degree
- A:
- 2
- B:
- 2
- C:
- 3
- D:
- 2
- E:
- 1
Odd or even
- A:
- Even
- B:
- Even
- C:
- Odd
- D:
- Even
- E:
- Odd
- 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.
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
In graph : is a path, is a cycle, and is a walk that is not a path, because is repeated.
Which is true of every path?
Connected graphs and trees
A tree is a connected graph with no cycles. A tree with vertices has exactly 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 , so at least one vertex has degree 1.
- Tree on vertices 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 edges.
A spanning tree of a connected graph includes every vertex and is a tree, so it has 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 .
- Complete graph, vertices edges
- Spanning tree edges
Worked example
A complete graph has 6 vertices. How many edges must be deleted to leave a spanning tree?
- 1
Edges in the complete graph: . Each vertex has degree 5.
- 2
A spanning tree has edges.
- 3
Edges to delete: .
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]
- [1]Degrees: P 2, Q 2, R 3, S 2, T 1.
- [1]A cycle, for example P → Q → R → P.
- [1]The graph contains a cycle.
- [1]A tree on 5 vertices has 4 edges, but this graph has 5.
That's the notes covered.
Carry on to the next subtopic.
Try a question
What is the degree of vertex ?
1 mark, marked against the mark scheme
What is the degree of vertex ?
1 mark, marked against the mark scheme