A Checklist for Reading a Graph List
A vertex-and-edge list is a complete description of a graph, but it does not always make the graph’s structure immediately apparent. A dependable classification comes from checking a few features in a consistent order: first the vertex set and degrees, then paths and cycles, then subgraphs, regularity and bipartiteness, and finally complements and possible isomorphisms. The checks reinforce one another: for example, a degree sequence can rule out an isomorphism, while a cycle can rule out bipartiteness.
All graphs in this tutorial are finite and simple: edges join two distinct vertices, and no pair of vertices has more than one edge. An edge \(12\) means the unordered pair \(\{1,2\}\). A path is a sequence of distinct vertices in which each consecutive pair is an edge. A cycle is a closed sequence of at least three edges whose vertices are distinct except for the repeated first and last vertex.
The distinction between subgraph and induced subgraph matters when classifying a list. A subgraph may omit edges whose endpoints it keeps; an induced subgraph may not. To find a complement, keep the original vertex set fixed and check every pair of distinct vertices exactly once.
Worked Example: One List, Several Features
Worked Example: Degrees, Induced Subgraphs and a Complement
Let \(G=(V,E)\), where \(V=\{1,2,3,4,5\}\) and \(E=\{12,23,34,14,13\}\). Classify its degrees, identify a path and cycles, decide whether it is regular or bipartite, and find an induced subgraph and its complement.
Count the edges incident with each vertex. Vertex \(1\) is incident with \(12,14,13\), so \(\deg(1)=3\). Vertex \(2\) is incident with \(12,23\), so \(\deg(2)=2\). Vertex \(3\) is incident with \(23,34,13\), so \(\deg(3)=3\). Vertex \(4\) is incident with \(34,14\), so \(\deg(4)=2\). Vertex \(5\) has no incident edge, so \(\deg(5)=0\). The degree sequence, written in decreasing order, is \((3,3,2,2,0)\); the graph is not regular because these degrees are not all equal.
The sequence \(1,2,3,4\) is a path: its successive edges \(12,23,34\) are all in \(E\), and its vertices are distinct. The vertices \(1,2,3\), together with \(12,23,13\), form a cycle of length \(3\). There is also the cycle \(1,2,3,4,1\), since \(12,23,34,14\in E\). The triangle shows that \(G\) is not bipartite: going around an odd cycle would require the two parts to alternate and return to the starting vertex in the opposite part.
For \(S=\{1,2,3\}\), the induced subgraph \(G[S]\) has the edges \(12,23,13\). These are all the listed edges with both endpoints in \(S\). In particular, \(G[S]\) is a triangle.
There are \(\binom{5}{2}=5\cdot4/2=10\) possible edges on \(V\). The five edges missing from \(E\) are \(15,24,25,35,45\), so these are precisely the edges of \(\overline{G}\). Its degrees are \(\deg_{\overline{G}}(1)=1\), \(\deg_{\overline{G}}(2)=2\), \(\deg_{\overline{G}}(3)=1\), \(\deg_{\overline{G}}(4)=2\), and \(\deg_{\overline{G}}(5)=4\).
Check: The degrees of \(G\) sum to \(3+2+3+2+0=10\), which is \(2|E|=2\cdot5=10\). The complement has \(5\) edges as well, and its degrees sum to \(1+2+1+2+4=10=2\cdot5\). Each original edge appears in exactly one of \(G\) and \(\overline{G}\).
What Features Tell Us About Isomorphism
An isomorphism is a bijection between vertex sets that preserves adjacency in both directions. In other words, distinct vertices \(u,v\) are adjacent in one graph exactly when their images are adjacent in the other. A useful test is to compare features an isomorphism must preserve: the number of vertices and edges, the degree sequence, and the presence or absence of cycles of a given length. A mismatch proves that two graphs are not isomorphic. A match does not, by itself, prove that they are isomorphic.
Proof. Let \(f:V(G)\to V(H)\) be an isomorphism. For any vertex \(v\), each neighbor \(u\) of \(v\) is mapped to a neighbor \(f(u)\) of \(f(v)\), because adjacency is preserved. Conversely, each neighbor of \(f(v)\) is \(f(u)\) for a unique vertex \(u\), since \(f\) is a bijection and preserves adjacency in both directions. Thus \(f\) gives a bijection from the neighbors of \(v\) to the neighbors of \(f(v)\), so \(\deg_G(v)=\deg_H(f(v))\). It follows that the degree sequences agree after sorting. Also, if \(v_1,\ldots,v_k,v_1\) is a cycle, then \(f(v_1),\ldots,f(v_k),f(v_1)\) is a cycle of the same length: consecutive vertices remain adjacent, and distinct vertices remain distinct under a bijection. Applying the inverse bijection gives the converse correspondence between cycles. Therefore the numbers of cycles of each length agree. \(\square\)
The degree sequence is a quick filter, not a complete classification tool. Even when two graphs pass that test, compare additional features, such as triangles, bipartiteness or the locations of vertices of a particular degree. When claiming that two graphs are isomorphic, give a bijection and verify which edges it maps to which edges.
Worked Example: Same Degrees, Different Graphs
Let \(P\) have vertex set \(\{1,2,3,4,5,6\}\) and edge set \(\{12,23,31,45,56,64,14,25,36\}\). Let \(K\) have vertex set \(\{a,b,c,x,y,z\}\) and edge set \(\{ax,ay,az,bx,by,bz,cx,cy,cz\}\). Determine whether the graphs are isomorphic.
In \(P\), vertices \(1,2,3\) form a triangle and vertices \(4,5,6\) form another triangle. Each vertex also has one edge to the other triangle: \(14,25,36\). Thus every vertex has degree \(3\), and \(P\) has \(9\) edges. In \(K\), every vertex in \(\{a,b,c\}\) is adjacent to all three vertices in \(\{x,y,z\}\), and there are no edges within either part. So \(K\) also has \(6\) vertices, \(9\) edges and degree \(3\) at each vertex.
Despite these matching counts and degrees, the graphs are not isomorphic. The graph \(P\) contains the triangle \(1,2,3,1\). The graph \(K\) is bipartite with parts \(\{a,b,c\}\) and \(\{x,y,z\}\), so it contains no triangle: among any three vertices, at least two belong to the same part, and those two are not adjacent. By the theorem, isomorphic graphs must agree on whether they contain a triangle. Hence \(P\) and \(K\) are not isomorphic.
Check: For \(P\), the degree sum is \(6\cdot3=18\), and twice its edge count is \(2\cdot9=18\). For \(K\), each of its two parts contributes \(3\cdot3=9\) edges, giving \(9\) edges total; its degree sum is again \(6\cdot3=18=2\cdot9\).
Confirming an Isomorphism
Worked Example: Matching Two Relabeled Lists
Let \(A\) have vertex set \(\{p,q,r,s\}\) and edge set \(\{pq,qr,rs,sp,pr\}\). Let \(B\) have vertex set \(\{1,2,3,4\}\) and edge set \(\{12,23,34,14,13\}\). Test whether the lists describe isomorphic graphs.
Consider the bijection \(f\) given by \(f(p)=1\), \(f(q)=2\), \(f(r)=3\), and \(f(s)=4\). Checking the edges one by one gives \(pq\mapsto12\), \(qr\mapsto23\), \(rs\mapsto34\), \(sp\mapsto41=14\), and \(pr\mapsto13\). These images are exactly the edges of \(B\).
To verify that no additional adjacency is being overlooked, the six possible pairs in \(A\) are \(pq,pr,ps,qr,qs,rs\). The listed edges are \(pq,pr,ps,qr,rs\), leaving only \(qs\) absent. In \(B\), the six possible pairs are \(12,13,14,23,24,34\); the listed edges are \(12,13,14,23,34\), leaving only \(24\) absent. The map sends \(qs\) to \(24\), so it preserves nonadjacency as well as adjacency. Therefore \(f\) is an isomorphism.
Check: In each graph the degree sequence is \((3,3,2,2)\): in \(A\), the degrees of \(p,q,r,s\) are \(3,2,3,2\); in \(B\), the degrees of \(1,2,3,4\) are \(3,2,3,2\). This necessary condition agrees with the explicit isomorphism.
A Reliable Classification Routine
For a small explicit graph, the following order keeps the checks manageable and makes it easier to spot omissions.
Include every listed vertex, even if no edge touches it. An isolated vertex affects the order, degree sequence and possible isomorphisms.
Write each degree before sorting the sequence. Check that the degree sum is \(2|E|\): each edge contributes one to the degree of each of its two endpoints.
Verify a proposed path or cycle by checking every required edge in the list. A missing edge breaks the proposed structure.
Regularity requires every degree to be equal. A proposed bipartition must place the endpoints of every edge in opposite parts; an odd cycle rules out bipartiteness.
For an induced subgraph, retain all listed edges whose endpoints both lie in the chosen vertex set. For a complement, list the absent pairs on the full original vertex set.
Use order, size and degree sequence to rule out impossible isomorphisms. To establish one, specify a bijection and check adjacency and nonadjacency.
The degree check in Step 2 is the handshake lemma: for every finite simple graph, the sum of the degrees equals twice the number of edges. To see why, count incidences consisting of a vertex and an edge containing it. Counting by vertices gives the degree sum; counting by edges gives two incidences per edge, since each edge has two distinct endpoints.
Proof. Fix a vertex \(v\). There are \(n-1\) other vertices. For each of them, exactly one of \(G\) and \(\overline{G}\) contains the edge to \(v\). Therefore \(\deg_G(v)+\deg_{\overline{G}}(v)=n-1\), which gives the formula. If \(G\) is \(r\)-regular, then every vertex of \(\overline{G}\) has degree \(n-1-r\), so the complement is regular. Conversely, if the complement is regular, the same formula gives the same degree \(n-1-\deg_{\overline{G}}(v)\) for every vertex of \(G\), so \(G\) is regular. This argument also includes \(n=0\): both graphs have no vertices, and regularity holds vacuously because there are no vertices with unequal degrees. \(\square\)
Common Pitfalls
Omitting an edge from an induced subgraph. In the first example, the vertex set \(S=\{1,2,3\}\) has all three edges \(12,23,13\) in \(G[S]\). Writing only \(12,23\) describes a subgraph of \(G\), but not the induced subgraph on \(S\). The correction is to inspect every pair inside \(S\) and include it exactly when it is an edge of \(G\).
Confusing matching invariants with a proof of isomorphism. The prism graph and \(K_{3,3}\) have the same order, size and degree sequence, yet they are not isomorphic because one has a triangle and the other has none. Matching basic counts is evidence that a comparison is worth pursuing, not a proof that the graphs are the same up to relabeling.
Forgetting isolated vertices or changing the vertex set of a complement. In the first example, vertex \(5\) has degree zero in \(G\), but degree four in \(\overline{G}\). The complement still has all five vertices; it does not discard an isolated vertex or introduce a new one.
Check Your Understanding
For each question, use the vertex and edge lists explicitly; when comparing graphs, distinguish a necessary test from a proof of isomorphism.
- For \(V=\{a,b,c,d\}\) and \(E=\{ab,bc,cd\}\), find the degree sequence and decide whether the graph is regular or bipartite.
- For the same graph and \(S=\{a,b,c\}\), list the edges of the induced subgraph \(G[S]\). Give an example of a subgraph on \(S\) that is not induced.
- For \(V=\{1,2,3,4\}\) and \(E=\{12,23,34,41\}\), list the edges of the complement and check the degrees in both graphs.
- Explain why the degree sequence alone does not prove that two graphs are isomorphic, using the two graphs from the worked comparison.
- Give a bijection that proves the graph on \(\{u,v,w\}\) with edges \(\{uv,vw,uw\}\) is isomorphic to the graph on \(\{1,2,3\}\) with edges \(\{12,23,13\}\), and verify the edge images.