Language and properties of graphs
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 .
- 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 . 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 vertex and edge each time.
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, is a trail: no edge is repeated, although vertices , and are visited more than once. A path repeats no vertex and a cycle is a closed path.
| Walk | Trail | Path | Cycle | |
|---|---|---|---|---|
| Edges may repeat | Yes | No | No | No |
| Vertices may repeat | Yes | Yes | No | Start only |
| Must be closed | No | No | No | Yes |
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 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 , so it is semi-Eulerian, with trails from to . Adding a second edge would make every degree even.
| 0 odd vertices | 2 odd vertices | More than 2 | |
|---|---|---|---|
| Type | Eulerian | Semi-Eulerian | Neither |
| Trail using every edge once | Closed, any start | Starts and ends at the odd vertices | None exists |
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 . 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 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 is Hamiltonian, but four vertices are odd, so it is not Eulerian.
A graph has a vertex of degree . Can it be Hamiltonian?
Try an exam question
A connected graph has five vertices with degrees , , , and . Find the number of edges, and state with a reason whether the graph is Eulerian, semi-Eulerian or neither.
[4 marks]
- [1]The sum of the degrees is .
- [1]Number of edges .
- [1]Exactly two vertices (the two of degree ) have odd degree.
- [1]So the graph is semi-Eulerian.
That's the notes covered.
Carry on to the next subtopic.
Try a question
Write down the degree of vertex .
1 mark, marked against the mark scheme
Write down the degree of vertex .
1 mark, marked against the mark scheme