Bipartite graphs, trees and regular graphs
Master bipartite graphs, trees and regular graphs in Year 11 VCE Specialist Mathematics. These are three key families of simple graph: bipartite (2-colourable) graphs, trees (connected and acyclic), and regular graphs in which every vertex has the same degree. It sits in the Algebra, number and structure area of study of the VCE Mathematics Study Design (VCAA), within the Graph theory topic of Unit 1.
You will learn to count edges with \(mn\) for the complete bipartite graph \(K_{m,n}\), \(n-1\) for a tree and \(\dfrac{nr}{2}\) for an \(r\)-regular graph, recognise the Platonic graphs, and apply the handshaking lemma to check each result.
Theory
This page introduces three families of simple graphs met in Year 11 Specialist Mathematics. A bipartite graph has its vertices split into two parts so that every edge joins the two parts (its vertices are 2-colourable); the complete bipartite graph \(K_{m,n}\) has \(mn\) edges. A tree is a connected graph with no cycles, and a tree on \(n\) vertices has exactly \(n-1\) edges. A regular graph has every vertex of the same degree \(r\), giving \(\dfrac{nr}{2}\) edges — the family that includes the Platonic graphs.
A bipartite graph is a graph whose vertices can be split into two parts so that every edge joins a vertex in one part to a vertex in the other, and no edge joins two vertices in the same part. Equivalently, the vertices can be coloured with just two colours so that no edge joins same-coloured vertices — the graph is 2-colourable.
The complete bipartite graph \(K_{m,n}\) has one part of \(m\) vertices and one part of \(n\) vertices, with every vertex in the first part joined to every vertex in the second. Because each of the \(m\) vertices contributes \(n\) edges, \(K_{m,n}\) has \(mn\) edges.
A tree is a graph that is connected (there is a path between every pair of vertices) and acyclic (it contains no cycles). A tree on \(n\) vertices has exactly \(n-1\) edges; since a tree already has one path between any two vertices, adding any single edge creates exactly one cycle. Equivalently, a connected simple graph on \(n\) vertices is a tree precisely when it has \(n-1\) edges.
A regular graph is one in which every vertex has the same degree \(r\); it is called \(r\)-regular. By the handshaking lemma the sum of all the vertex degrees equals twice the number of edges, so an \(r\)-regular graph on \(n\) vertices has \(\dfrac{nr}{2}\) edges (and \(nr\) must be even). The Platonic graphs are regular examples: the tetrahedron and the cube are \(3\)-regular, and the octahedron is \(4\)-regular.
Each graph family gives a quick way to count edges. For the complete bipartite graph with parts of size \(m\) and \(n\):
For a tree on \(n\) vertices the number of edges is fixed:
For a regular graph in which every one of the \(n\) vertices has degree \(r\):
Both edge formulas follow from the handshaking lemma: the sum of all vertex degrees is twice the number of edges,
Identifying the family and counting edges
- Bipartite? Try to two-colour the vertices so that no edge joins same-coloured vertices. If you can, the graph is bipartite; if every vertex of one part joins every vertex of the other, it is the complete bipartite graph \(K_{m,n}\) with \(mn\) edges.
- Tree? Check it is connected and has no cycle. A connected graph on \(n\) vertices is a tree exactly when it has \(n-1\) edges, so use \(E=n-1\) (or rearrange to \(n=E+1\)).
- Regular? Check every vertex has the same degree \(r\). Then the number of edges is \(\dfrac{nr}{2}\); rearrange to find \(n\) or \(r\) if an edge count is given.
- Check with handshaking. Confirm the sum of degrees equals \(2E\); for a regular graph this is just \(nr=2E\), and \(nr\) must be even.
For example, a \(3\)-regular graph on \(6\) vertices has \(\dfrac{6\times 3}{2}=9\) edges, and the sum of its degrees is \(6\times 3=18=2\times 9\), as the handshaking lemma requires.
A tree on \(n\) vertices has exactly \(n-1\) edges:
| \(\text{edges}\) | \(=\) | \(n-1\) |
| \(=\) | \(7-1\) | |
| \(=\) | \(6\) |
A tree with \(7\) vertices has \(6\) edges.
The complete bipartite graph \(K_{m,n}\) has \(mn\) edges — multiply the two part sizes:
| \(\text{edges}\) | \(=\) | \(m \times n\) |
| \(=\) | \(2 \times 4\) | |
| \(=\) | \(8\) |
\(K_{2,4}\) has \(8\) edges.
A regular graph on \(n\) vertices each of degree \(r\) has \(\dfrac{nr}{2}\) edges:
| \(\text{edges}\) | \(=\) | \(\dfrac{nr}{2}\) |
| \(=\) | \(\dfrac{6 \times 4}{2}\) | |
| \(=\) | \(\dfrac{24}{2}\) | |
| \(=\) | \(12\) |
The octahedron has \(12\) edges.
Set \(\dfrac{nr}{2}\) equal to the number of edges with \(r=3\), then solve for \(n\):
| \(\dfrac{nr}{2}\) | \(=\) | \(15\) |
| \(\dfrac{n \times 3}{2}\) | \(=\) | \(15\) |
| \(3n\) | \(=\) | \(30\) |
| \(n\) | \(=\) | \(10\) |
Check with the handshaking lemma (sum of degrees \(=2E\)):
| \(\text{sum of degrees}\) | \(=\) | \(nr = 10 \times 3 = 30\) |
| \(2E\) | \(=\) | \(2 \times 15 = 30\) |
The graph has \(10\) vertices.
Common pitfalls
Frequently asked questions
What is a bipartite graph?
A graph whose vertices can be split into two parts so that every edge joins a vertex in one part to a vertex in the other, and no edge joins two vertices in the same part. Equivalently, its vertices can be 2-coloured with no edge joining same-coloured vertices.
How many edges does the complete bipartite graph \(K_{m,n}\) have?
It has \(mn\) edges. Each of the \(m\) vertices in one part is joined to all \(n\) vertices in the other part, so \(K_{3,4}\) has \(3\times 4=12\) edges.
How many edges does a tree have?
A tree on \(n\) vertices always has exactly \(n-1\) edges. A connected simple graph on \(n\) vertices is a tree precisely when it has \(n-1\) edges, and adding any further edge creates exactly one cycle.
How many edges does a regular graph have?
An \(r\)-regular graph on \(n\) vertices has \(\dfrac{nr}{2}\) edges, which follows from the handshaking lemma \(\sum\deg(v)=2E\). The product \(nr\) must be even for such a graph to exist.
What are the Platonic graphs?
They are the graphs of the five Platonic solids and are all regular. The tetrahedron and cube are \(3\)-regular, and the octahedron is \(4\)-regular, so they are standard examples of regular graphs.
What is the handshaking lemma?
The sum of all the vertex degrees in a graph equals twice the number of edges: \(\sum\deg(v)=2E\). It underlies both the tree count \(n-1\) and the regular count \(\dfrac{nr}{2}\).