Two teams describe the same kind of network using different names. The first lists vertices 1, 2, 3, 4 and edges 12, 23, 34, 41, 13. The second lists vertices a, b, c, d and edges ac, ad, bd, bc, cd. Does relabeling explain the difference, or does one network contain a different connection?
Here an edge such as 12 is the unordered pair consisting of vertices 1 and 2, not the number twelve. We work with finite simple undirected graphs: no loops, repeated edges or arrow directions. Vertex positions and line lengths in a drawing are not data. Crossing lines create no extra vertex unless a vertex is explicitly marked there.
Try the map f(1)=c, f(2)=a, f(3)=d, f(4)=b. First check that each target name occurs exactly once. This proves f is a bijection. Now track both endpoints of every source edge, instead of comparing the overall appearance of pictures.
Predict
The five edges map to ca, ad, db, bc, cd, exactly the target edge list. There is one remaining unordered source pair, 24, which maps to ab. Neither is an edge. We have checked all six unordered pairs, so the map preserves both edges and nonedges.
An isomorphism is a vertex bijection f such that, for every pair of distinct vertices u,v,
uv is an edge in G if and only if f(u)f(v) is an edge in H.
The reverse direction matters. Predict whether the identity map from a three-vertex path with edges 12,23 to a triangle with edges 12,23,13 is an isomorphism. Every source edge survives, but source nonedge 13 becomes an edge. An edge-preserving bijection alone is therefore not enough in general.
Before proceeding, write the difference between these claims: “I found a bijection that works” and “I tried one bijection that failed.” The first proves isomorphism; the second refutes only that candidate, not every possible relabeling.
Experiment
Now inspect two graphs with the same degree sequence. A vertex’s degree is its number of neighbors. Predict every degree before tracing connectivity. Do not count a line crossing or the length of an edge as another connection.
Left edges: 12,23,34,45,56,61. Right edges: ab,bc,ca,de,ef,fd. No other pairs are edges. The placement distinguishes components but does not assign geometric meaning to distances.
Compute these properties from the edge lists, not just the drawings.
Property
Six-cycle
Two triangles
Vertices
6
6
Edges
6
6
Sorted degrees
2,2,2,2,2,2
2,2,2,2,2,2
Connected components
1
2
Attempt to map consecutive vertices of the cycle to the right graph. After choosing an image for vertex 1, every next image along the cycle must stay in that same triangle. Why can a bijection not finish? The obstacle is structural: no path joins the two target components.
Understand
An isomorphism invariant is a property unchanged by every isomorphism. Prove this before using it to rule out all bijections. For degree, f sends the neighbors of u bijectively to the neighbors of f(u): edge preservation gives one inclusion, and the inverse map gives the other. Their finite counts agree. Thus degree sequence is necessary for isomorphism.
For connectedness, applying f to successive vertices of a path gives a path in the target. Applying its inverse takes target paths back to source paths. Consequently two vertices are connected by a path exactly when their images are, so components correspond bijectively. The preceding graphs cannot be isomorphic because their component counts differ. Agreement of degrees and sizes supplied necessary conditions, not a sufficient certificate.
Even adding connectedness does not finish classification. Compare a triangular prism with vertices a,b,c,A,B,C and edges ab,bc,ca,AB,BC,CA,aA,bB,cC, with the complete bipartite graph K₃,₃. The latter has parts u,v,w and x,y,z and all nine cross-part edges. Both are connected, have six vertices and nine edges, and every vertex has degree three. The prism contains triangle abc. K₃,₃ has none: among any three vertices, two are in the same part and are not adjacent. A bijection preserving edges would carry a triangle to three distinct pairwise adjacent vertices, which is impossible here. This is a new invariant certificate, not proof that the enlarged invariant list classifies every graph.
There is a useful finite shortcut for checking a proposed bijection. If the two graphs have equal edge counts and every source edge maps to a target edge, then nonedges are preserved automatically. A vertex bijection induces an injective map on unordered pairs. Therefore its edge image is a subset of the target edges of the same finite size, hence the whole edge set. No nonedge can map to a target edge with an already occupied unique preimage. This shortcut uses equal finite edge counts as well as the proposed map; equal edge counts alone prove nothing of the kind.
The matrix form makes the two-endpoint rule precise. Order the source vertices 1 through n and the target vertices 1 through n. Let A and B be their adjacency matrices, where entry (i,j) is 1 exactly when that pair is an edge. Define the permutation matrix P by placing a 1 in row f(i), column i, with all other entries zero. Then B=PAPᵀ: the (r,s) entry is A at row f⁻¹(r), column f⁻¹(s). The superscript T means transpose, interchanging rows and columns. Relabeling changes both endpoints, so it permutes rows and columns together. Permuting rows alone is not the same operation. The written task works through the full three-vertex matrices; no matrix multiplication is needed for the edge-list certificates above.
Apply
Create a new labeling of the initial four-vertex graph using names w,x,y,z. Write the mapping first, generate all five target edges, then ask another learner to recover an isomorphism from just the edge lists. Their map need not equal yours: symmetries can produce several valid bijections. Verify whichever map they supply rather than comparing its spelling with one expected answer.
Next audit this proposed rule: “If degree sequence, edge count and connectedness agree, accept.” Use the connected regular counterexample above to refute the rule. Then repair the algorithm without claiming a fast solution: enumerate all vertex bijections and test every unordered pair for each one. A passing bijection is a certificate. If all fail, every possible isomorphism has been excluded. There are n! bijections and n(n−1)/2 pairs, giving at most n!·n(n−1)/2 pair tests, apart from enumeration and bookkeeping. This upper bound describes this particular exhaustive method; it is not a lower bound on all isomorphism algorithms.
Include small boundaries in your explanation. For zero vertices there is one empty bijection; for one vertex there is one possible bijection. In either case no pair tests are required, and simple graphs of that same size are isomorphic. Reject unequal vertex counts before starting the enumeration.
Continue
In the practice, provide either an explicit bijection with a complete verification, or a proved invariant that differs. A failed guess at a map is not a nonisomorphism proof. Conversely, several agreeing invariants are not a substitute for a working map unless a separate classification theorem establishes sufficiency for the graph family in question.
Keep graph identity separate from what later computations measure. Walk counts, degrees and adjacency matrices contain useful evidence, but interpreting each requires its own conventions and proof. State the graph model and the exact claim before choosing a certificate.
Apply · explain · revise
Practice and reasoning
Drafts save locally as you type. Reveal worked solutions when useful; the site remembers that exposure. Automatic matches check the requested answer, while written arguments require review against the rubric.
Graph G has vertices 1,2,3,4,5 and edges 12,23,31,34,45. Graph H has vertices u,v,w,z,t and edges vw,wz,zv,zu,ut. Construct two distinct isomorphisms G→H and verify one by checking all ten unordered vertex pairs. Explain why a picture that looks similar is not the certificate.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Let G,H be finite simple undirected graphs with the same number of vertices. Suppose a bijection f sends every edge of G to an edge of H. Is f necessarily an isomorphism? Give a counterexample with three vertices. Then prove that the additional assumption |E(G)|=|E(H)| makes this edge-only verification sufficient. Explain the role of finiteness.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Compare the six-cycle G with edges 12,23,34,45,56,61 and H with edges ab,bc,ca,de,ef,fd. Compute their degree sequences and edge counts. Prove they are not isomorphic using connectedness, and prove rather than assume that connectedness is preserved by an isomorphism.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
The triangular prism has vertices a,b,c,A,B,C and edges ab,bc,ca,AB,BC,CA,aA,bB,cC. The complete bipartite graph has parts {u,v,w} and {x,y,z}, with all nine cross-part edges and no within-part edges. Both graphs are connected. Verify their common degree sequence, then give a nonisomorphism certificate that still works after connectedness fails to distinguish them. Prove the invariant you use.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Use ordered vertices 1,2,3 for the path with edges 12 and 23. Relabel by f(1)=3,f(2)=1,f(3)=2, keeping target row/column order 1,2,3. Write A, the source adjacency matrix, and B, the target matrix. Define P by P[f(i),i]=1 and zeros elsewhere. Prove B=PAPᵀ. Explain why permuting only rows does not implement an undirected vertex relabeling.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
A classifier declares two finite simple undirected graphs isomorphic whenever vertex count, edge count, degree sequence and connectedness all agree. Refute its correctness with an explicit pair from this lesson and explain why adding a triangle count still would not itself prove a complete classification theorem. Design a correct always-terminating isomorphism decision procedure using vertex bijections; justify both answers and give an upper bound on the number of pair tests for n vertices, including n=0 or n=1.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Reflect and continue
Before marking this lesson complete, explain one key idea without the worked solution and identify a condition that matters. Marking complete records participation, not independent mastery.
