Computer Sciencehard
List of Vertex-Transitive Graphs on 8 Vertices - Isomorphism Classes
Question
Find the list of vertex-transitive graphs on 8 vertices. How many isomorphism classes () exist for each degree?
Enumeration of highly symmetric graphs using automorphism groups.
Total Vertex-Transitive Graphs on 8 Vertices
14
14 non-isomorphic vertex-transitive graphs across all degrees
1Define Vertex-Transitivity
A graph is **vertex-transitive** if for every pair of vertices there exists an automorphism of mapping to . All vertices are 'structurally identical' — the graph looks the same from any vertex.
Key Property
Vertex-transitivity implies regularity: every vertex has the same degree. But not all regular graphs are vertex-transitive — the automorphism group must act transitively on the vertex set.
2Approach to Enumeration
We check all possible regular graphs on 8 vertices and verify which have a transitive automorphism group. By complementation symmetry, (degree and degree graphs are in bijection).
3Classification by Degree
| Degree | Count Nⱼ | Examples | Notes |
|---|---|---|---|
| 0 | 1 | 8K₁ (empty graph) | Complement of K₈ |
| 1 | 1 | 4K₂ (perfect matching) | 4 disjoint edges |
| 2 | 2 | C₈, 2C₄ | Cycle(s) |
| 3 | 3 | Q₃, K₄₄−I, Möbius–Kantor-related | 3 graphs |
| 4 | 3 | K₄,₄, C₈(1,2), ... | Complement of d=3 |
| 5 | 2 | Complement of d=2 | |
| 6 | 1 | Complement of 4K₂ | Cocktail party graph |
| 7 | 1 | K₈ (complete graph) | All connected |
4Summary
Degree 01 graph
Degree 11 graph
Degree 22 graphs
Degree 33 graphs
Degree 43 graphs
Degree 52 graphs
Degree 61 graph
Degree 71 graph
TOTAL (all degrees)14 graphs
5Key Concepts
Complementation Symmetry
If is vertex-transitive on vertices with degree , then (the complement) is vertex-transitive with degree . This means , cutting the enumeration work in half.
Famous Examples
The cube graph (vertices = binary strings of length 3, edges between strings differing in one bit) is a classic vertex-transitive graph on 8 vertices with degree 3.
Quiz
Test your understanding with these questions.
1
Vertex-transitivity implies that the graph must be:
2
If there are vertex-transitive graphs of degree on 8 vertices, what is the relationship ?