Graph types and Eulerian graphs
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; vertices give edges.
- has edges; is planar, 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
- vertices, edges
Spanning tree
- A subgraph that is a tree
- Includes every vertex
A graph has 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 has edges.
A complete graph has vertices with every pair joined by exactly one edge. Each vertex has degree , so has edges. For example has edges and has edges.
- Edges of
- Degree of each vertex
Worked example
has edges. Find .
- 1
, so .
- 2
, which factorises as .
- 3
must be positive, so .
How many edges does 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. is planar, but 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.
Two graphs both have vertices and edges, but one has a vertex of degree 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 . Is it Eulerian, semi-Eulerian or neither?
- 1
Count the odd degrees: the two s.
- 2
Exactly two vertices are odd, so the graph is semi-Eulerian.
- 3
The trail must start at one vertex of degree and end at the other.
A connected graph has degrees . What is it?
Try an exam question
A connected graph has six vertices with degrees . Find the number of edges and state, with a reason, whether the graph is Eulerian, semi-Eulerian or neither.
[4 marks]
- [1]Sum of degrees , so there are edges.
- [1]Exactly two vertices have odd degree (the two of degree ).
- [1]So the graph is semi-Eulerian.
- [1]A route using every edge once must start at one vertex of degree and end at the other.
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
What is the sum of the degrees (orders) of the six vertices?
1 mark, marked against the mark scheme