Simple graphs, isomorphism, subgraphs and connectedness
Master simple graphs, isomorphism, subgraphs and connectedness in Year 11 VCE Specialist Mathematics. A simple graph has no loops or repeated edges, and two graphs are isomorphic when one can be relabelled to match the other exactly. 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 compare graphs by their degree sequence and other invariants, identify subgraphs, test connectedness and count components, and work with the complete graph \(K_n\) — which has \(\dfrac{n(n-1)}{2}\) edges — and the complement of a graph.
Theory
A simple graph is a set of vertices joined by edges, with no loops and no repeated edges. In Year 11 Specialist Mathematics you describe such graphs by their degree sequence, decide when two are isomorphic, pick out subgraphs, and test whether a graph is connected. The complete graph \(K_n\) has \(\dfrac{n(n-1)}{2}\) edges, and the complement supplies exactly the edges a graph is missing.
A graph is a collection of vertices (dots) joined by edges (lines). A simple graph has no loops (an edge from a vertex to itself) and no multiple edges (at most one edge between any pair of vertices).
The degree of a vertex is the number of edges meeting it. Listing the degrees from highest to lowest gives the degree sequence — a compact fingerprint of the graph. The handshaking lemma says the degrees add up to twice the number of edges, because every edge contributes \(1\) to each of its two endpoints.
Two graphs are isomorphic if one can be relabelled to match the other exactly — same vertices joined in the same pattern. Isomorphic graphs look different on the page but are structurally identical, so they must share every invariant: the same number of vertices, the same number of edges and the same degree sequence. If any one of these differs, the graphs are not isomorphic.
A subgraph is obtained by keeping some of the vertices and some of the edges of a graph. Every vertex and every edge of a subgraph must already belong to the original graph.
A graph is connected if you can travel between any two vertices along edges. Otherwise it splits into connected components — the separate pieces. A single vertex with no edges is a component on its own (an isolated vertex).
The complete graph \(K_n\) joins every pair of the \(n\) vertices exactly once. The complement \(\overline{G}\) of a graph \(G\) has the same vertices but exactly the edges that \(G\) is missing — together, \(G\) and \(\overline{G}\) make up the complete graph.
The complete graph \(K_n\) joins every pair of \(n\) vertices exactly once, so its edge count is the number of pairs:
The handshaking lemma links the degrees to the edge count — each edge adds \(1\) to two vertices:
The complement \(\overline{G}\) has every edge \(G\) is missing from the complete graph, so on \(n\) vertices:
How to analyse a simple graph
- Check it is simple: no loops and no repeated edges between the same pair of vertices.
- Find each degree: count the edges meeting each vertex, then list the degrees from highest to lowest to get the degree sequence (include a \(0\) for any isolated vertex).
- Count edges quickly: for a complete graph use \(\dfrac{n(n-1)}{2}\); otherwise use the handshaking lemma \(|E|=\tfrac{1}{2}\sum \deg(v)\).
- Test isomorphism: compare the vertex count, edge count and degree sequence of the two graphs. If any differ, they are not isomorphic.
- Test connectedness: group vertices that can reach one another. One group means the graph is connected; several groups are the connected components.
- Complement: take the same vertices but only the missing edges — \(\dfrac{n(n-1)}{2}-|E|\) of them.
A complete graph joins every pair of vertices exactly once, so count the pairs:
| \(\text{edges}\) | \(=\) | \(\dfrac{n(n-1)}{2}\) |
| \(=\) | \(\dfrac{5 \times 4}{2}\) | |
| \(=\) | \(\dfrac{20}{2}\) | |
| \(=\) | \(10\) |
\(K_5\) has \(10\) edges.
Count the edges meeting each vertex:
| \(\deg C\) | \(=\) | \(3 \quad (\text{joined to } A, B, D)\) |
| \(\deg A = \deg B = \deg D\) | \(=\) | \(2\) |
| \(\deg E\) | \(=\) | \(1\) |
List the degrees from highest to lowest:
| \(\text{degree sequence}\) | \(=\) | \((3,2,2,2,1)\) |
A graph is isomorphic to \(G\) only if it matches every invariant: \(5\) vertices, \(5\) edges and the degree sequence \((3,2,2,2,1)\).
The degree sequence is \((3,2,2,2,1)\); an isomorphic graph must share all three invariants.
The complement holds exactly the edges \(G\) is missing from the complete graph \(K_6\):
| \(\text{edges of } K_6\) | \(=\) | \(\dfrac{6 \times 5}{2} = 15\) |
| \(\text{edges of } \overline{G}\) | \(=\) | \(15 - 7\) |
| \(=\) | \(8\) |
The complement \(\overline{G}\) has \(8\) edges.
Group the vertices that can reach one another:
| \(\{A,B,C\}\) | \(&\) | \(\text{triangle } AB, BC, CA\) |
| \(\{D,E\}\) | \(&\) | \(\text{single edge } DE\) |
| \(\{F\}\) | \(&\) | \(\text{isolated vertex}\) |
There are three separate pieces, so join them up:
| \(\text{components}\) | \(=\) | \(3\) |
| \(\text{edges to add}\) | \(=\) | \(3 - 1 = 2\) |
\(H\) is not connected: it has \(3\) components, and \(2\) edges must be added to connect it.
Common pitfalls
Frequently asked questions
What is a simple graph?
A simple graph is a set of vertices joined by edges with no loops (no edge from a vertex to itself) and no multiple edges (at most one edge between any pair of vertices).
When are two graphs isomorphic?
Two graphs are isomorphic when one can be relabelled to match the other exactly. They must share every invariant: the same number of vertices, the same number of edges and the same degree sequence.
What is a degree sequence and why does it matter?
The degree sequence lists the vertex degrees from highest to lowest, e.g. \((3,2,2,2,1)\). It is an isomorphism invariant: if two graphs have different degree sequences they cannot be isomorphic.
How many edges does the complete graph \(K_n\) have?
Because every pair of the \(n\) vertices is joined exactly once, \(K_n\) has \(\dfrac{n(n-1)}{2}\) edges. For example \(K_5\) has \(10\) and \(K_6\) has \(15\).
What is the complement of a graph?
The complement \(\overline{G}\) keeps the same vertices but has exactly the edges \(G\) is missing. On \(n\) vertices it has \(\dfrac{n(n-1)}{2}-|E|\) edges, and together \(G\) and \(\overline{G}\) form the complete graph.
What does it mean for a graph to be connected?
A graph is connected if you can travel between any two vertices along edges. If not, it breaks into separate pieces called connected components; an isolated vertex is a component by itself.