Building Regular Graphs from Edge Lists
A degree condition tells us how many neighbors each vertex must have, but it does not prescribe which vertices are joined. Different choices of edges can therefore produce different regular graphs with the same number of vertices. This tutorial develops that idea through explicit small constructions: first 2-regular graphs, then 3-regular graphs. In each case, the edge list will make the construction precise, and degree counts and structural checks will verify it.
To check regularity from an edge list, inspect each vertex and count the listed edges containing it. For an \(r\)-regular graph of positive order \(n\), the degree sum is \(rn\). Each edge contributes one to the degree of each of its two endpoints, so the degree sum is also \(2m\). Consequently, any such graph must satisfy
The final inequality follows because a vertex in a simple graph can be adjacent to at most the other \(n-1\) vertices. These conditions are useful checks on a proposed construction; by themselves, they do not specify which edges to choose or guarantee a particular structure.
Two Different 2-Regular Graphs
In a 2-regular graph, every vertex must occur in exactly two edges. A convenient construction on six vertices is to arrange the vertices in a cycle. A different edge choice is to make two separate triangles. Both choices use six vertices and six edges, but their triangle structures differ.
Worked Example: A 6-Cycle and Two Triangles
First define \(G_1=(V_1,E_1)\) by \(V_1=\{1,2,3,4,5,6\}\) and \(E_1=\{12,23,34,45,56,61\}\). The listed edges join consecutive vertices around the cycle, including \(6\) to \(1\). Counting incident edges gives \(\deg(1)=2\) from \(12,61\), \(\deg(2)=2\) from \(12,23\), \(\deg(3)=2\) from \(23,34\), \(\deg(4)=2\) from \(34,45\), \(\deg(5)=2\) from \(45,56\), and \(\deg(6)=2\) from \(56,61\). Thus \(G_1\) is 2-regular and has six edges.
Now define \(G_2=(V_2,E_2)\) by \(V_2=\{1,2,3,4,5,6\}\) and \(E_2=\{12,23,31,45,56,64\}\). The first three edges form a triangle on \(\{1,2,3\}\); the last three form a triangle on \(\{4,5,6\}\). Vertices \(1,2,3\) each occur in exactly two of the first three edges, and vertices \(4,5,6\) each occur in exactly two of the last three edges. Therefore every vertex has degree \(2\), and \(G_2\) also has six edges.
Check: In either graph, the degree sum is \(6\cdot2=12\), and the edge list has \(6\) edges, contributing \(2\cdot6=12\) to the degree sum. The two edge lists do describe different graphs up to isomorphism: \(G_1\) has no triangle, while \(G_2\) has two. For \(G_1\), each vertex’s two neighbors are not adjacent to one another, so no three vertices form a triangle; in \(G_2\), \(1,2,3\) and \(4,5,6\) each form one.
The comparison illustrates an important construction principle: specifying only the degree of each vertex does not generally determine the graph. Even when both graphs have the same order, size, and degree at every vertex, an additional structural feature may distinguish them.
Two Different 3-Regular Graphs on Six Vertices
For a 3-regular graph on six vertices, the degree-sum calculation requires \(6\cdot3=18\), so there must be \(18/2=9\) edges. We will construct two graphs meeting that count. One joins every vertex in one group to all three vertices in another group. The other consists of two triangles with corresponding vertices joined by three additional edges.
Worked Example: The Complete Bipartite Graph \(K_{3,3}\)
Define \(H_1=(V_1,E_1)\) with \(V_1=\{a,b,c,x,y,z\}\) and \(E_1=\{ax,ay,az,bx,by,bz,cx,cy,cz\}\). There are no edges within \(\{a,b,c\}\) or within \(\{x,y,z\}\). Each of \(a,b,c\) is incident to the three edges joining it to \(x,y,z\); each of \(x,y,z\) is incident to the three edges joining it to \(a,b,c\). Thus all six vertices have degree \(3\). This is \(K_{3,3}\), with the two displayed sets as its parts.
Check: The edge list contains three edges incident to each of \(a,b,c\), for \(3\cdot3=9\) edges in total. The degrees sum to \(6\cdot3=18\), and the nine listed edges contribute \(2\cdot9=18\). Every edge joins the two parts, so a triangle cannot occur: as you follow successive edges, the vertices must alternate between the parts, and after three edges you cannot return to the starting part.
Worked Example: A Triangular Prism Graph
Define \(H_2=(V_2,E_2)\) with \(V_2=\{1,2,3,4,5,6\}\) and \(E_2=\{12,23,31,45,56,64,14,25,36\}\). The first three edges form a triangle on \(\{1,2,3\}\), and the next three form a triangle on \(\{4,5,6\}\). The remaining edges \(14,25,36\) join corresponding vertices of those triangles.
For the degree check, vertices \(1,2,3\) have neighbor sets \(\{2,3,4\}\), \(\{1,3,5\}\), \(\{1,2,6\}\), respectively. Vertices \(4,5,6\) have neighbor sets \(\{5,6,1\}\), \(\{4,6,2\}\), \(\{4,5,3\}\), respectively. Each set has three distinct vertices, so \(H_2\) is 3-regular. It has six vertices and nine listed edges.
Check: The degree sum is \(6\cdot3=18\), and counting the displayed edge list gives \(3+3+3=9\) edges, whose endpoints contribute \(2\cdot9=18\) degrees in total. The graph contains the triangles \(1,2,3,1\) and \(4,5,6,4\).
Both 3-regular examples have order \(6\) and size \(9\). Their degree data agree exactly, but their triangle structures do not: \(H_1\) has no triangle, whereas \(H_2\) has at least two. The next result explains why this difference proves that the graphs are not isomorphic.
Using Triangles to Compare Constructions
Proof. Let \(G\) and \(H\) be isomorphic, and let \(f:V(G)\to V(H)\) be an isomorphism. By definition, \(f\) is a bijection and \(uv\in E(G)\) exactly when \(f(u)f(v)\in E(H)\). If \(u,v,w\) form a triangle in \(G\), then \(uv,vw,wu\in E(G)\), so \(f(u)f(v),f(v)f(w),f(w)f(u)\in E(H)\). The three image vertices are distinct because \(f\) is a bijection; hence they form a triangle in \(H\). Conversely, applying the same reasoning to the inverse bijection \(f^{-1}\) shows that every triangle in \(H\) comes from a triangle in \(G\). Thus \(f\) gives a bijection between the triangles of the graphs, and their numbers of triangles are equal. \(\square\)
For \(H_1=K_{3,3}\), the two parts contain all vertices and every edge joins different parts. A triangle would have to cross between the parts three times and return to its starting part, which is impossible: after an odd number of crossings it is in the other part. Thus \(H_1\) has zero triangles.
For \(H_2\), there are exactly two triangles. To verify that there are no others, inspect the neighbors of each vertex. Among the neighbors of \(1\), namely \(2,3,4\), only \(2\) and \(3\) are adjacent. Among the neighbors of \(2\), namely \(1,3,5\), only \(1\) and \(3\) are adjacent. Among the neighbors of \(3\), namely \(1,2,6\), only \(1\) and \(2\) are adjacent. These give the same triangle \(1,2,3\). Among the neighbors of \(4\), namely \(5,6,1\), only \(5\) and \(6\) are adjacent; among the neighbors of \(5\), namely \(4,6,2\), only \(4\) and \(6\) are adjacent; among the neighbors of \(6\), namely \(4,5,3\), only \(4\) and \(5\) are adjacent. These give the same triangle \(4,5,6\). Every triangle containing a vertex must use an adjacent pair among its neighbors, so this inspection accounts for all of them. The proposition now shows that \(H_1\) and \(H_2\) are not isomorphic.
A Degree-Count Result for Construction Checks
Proof. Count the incidences between vertices and edges in two ways. Each of the \(n\) vertices has degree \(r\), so counting by vertices gives \(rn\) incidences. Each of the \(m\) edges has two distinct endpoints, because the graph is simple, so counting by edges gives \(2m\) incidences. These count the same vertex-edge pairs, hence \(rn=2m\). Since \(2m\) is even, \(rn\) is even. \(\square\)
This proposition is a check, not a construction recipe on its own. For instance, it predicts nine edges for a 3-regular graph on six vertices, and the two examples above each have exactly nine. But an edge list must still be checked vertex by vertex: an incorrect list might have nine edges without giving degree \(3\) at every vertex.
Common Pitfall: Confusing the Degree Sum with the Edge Count
A frequent counting error is to claim that a 2-regular graph on six vertices needs twelve edges because its degree sum is \(6\cdot2=12\). That number is the sum of the degrees, not the number of edges. Every edge is counted at both endpoints, so the edge count is \(12/2=6\). The \(C_6\) example confirms this directly: its six listed edges contribute twelve total degrees.
The same correction applies to the 3-regular examples: six vertices of degree \(3\) have degree sum \(18\), so the required number of edges is \(18/2=9\), not \(18\). Always divide the degree sum by two when counting edges in a finite simple undirected graph.
When comparing constructions, use the degree count to catch arithmetic errors, then inspect the actual edge structure. In the examples here, the degree counts verify regularity and the triangle counts distinguish non-isomorphic graphs. Neither check replaces the other: an edge total alone does not verify every degree, and matching degrees do not establish that two graphs are isomorphic.
Check Your Understanding
For each question, use explicit vertices and edges or the degree-count argument to justify your answer.
- How many edges must a 2-regular graph on eight vertices have? State the degree sum used.
- Give an edge list for a 2-regular graph on four vertices and verify the degree of every vertex.
- Why can \(K_{3,3}\) not be isomorphic to the triangular prism graph, even though both have six vertices and are 3-regular?
- A proposed 3-regular graph on six vertices has eight edges. What check shows that the proposal cannot be correct?
- Explain why equal order, size, and degree at every vertex do not by themselves prove that two graphs are isomorphic.