Using Graphs to Compare Molecular Structures
A molecular formula tells us which atoms a molecule contains, but not how they are connected. Graphs record that connectivity: atoms are vertices and bonds are edges. Two candidate structures with the same formula may therefore be compared by asking whether their molecular graphs are isomorphic. Invariants such as vertex counts, degree sequences and cycle counts can quickly rule out isomorphism. They are useful filters, but passing those tests does not always settle the question; a final comparison may require an explicit correspondence between vertices and their adjacencies.
We use finite simple graphs for the carbon skeletons below. To record a general molecular structure, attach an atom label, such as C or O, to each vertex and a bond label, such as single or double, to each edge. An isomorphism of molecular graphs must preserve both kinds of labels. In the hydrocarbon examples, all displayed vertices represent carbon atoms, all displayed edges represent single bonds, and hydrogen atoms are implicit. Thus a carbon vertex of degree \(d\) has \(4-d\) attached hydrogens, provided \(d\leq 4\). This convention is only being used for these single-bond carbon skeletons.
A graph invariant is a quantity that has the same value on isomorphic graphs. If two graphs have different values of even one invariant, they cannot be isomorphic. The converse is not generally true: two graphs can agree on several invariants and still have different adjacency patterns.
What Isomorphisms Must Preserve
Proof. Let \(f:V(G)\to V(H)\) be an isomorphism. Since \(f\) is a bijection, \(|V(G)|=|V(H)|\). It sends each edge of \(G\) to an edge of \(H\), and the inverse bijection sends each edge of \(H\) back to an edge of \(G\). Thus the edge correspondence is a bijection, so \(|E(G)|=|E(H)|\). For any vertex \(v\), the map \(f\) sends the neighbors of \(v\) bijectively to the neighbors of \(f(v)\), so \(\deg_G(v)=\deg_H(f(v))\). Consequently the multisets of vertex degrees agree. Finally, applying \(f\) to the vertices of a cycle of length \(k\) gives a cycle of length \(k\) in \(H\); applying \(f^{-1}\) reverses this correspondence. The number of cycles of each length therefore agrees. Preservation of atom and bond labels is required by the definition of labeled isomorphism. \(\square\)
The degree sequence is the list of vertex degrees arranged in nonincreasing order, with repetitions included. Sorting the degrees matters: the names assigned to vertices in an edge list are arbitrary, so a degree attached to vertex \(1\) in one description need not correspond to the degree attached to vertex \(1\) in another.
Adjacency lists give a direct way to check the remaining structure. The lists must be compared after a proposed bijection of vertices: each vertex must have exactly the neighbors corresponding to its neighbors in the other graph. Equivalently, if vertices are ordered and \(A_G,A_H\) are their adjacency matrices, an isomorphism corresponds to a simultaneous permutation of rows and columns that makes the adjacency data agree. A matrix written in one arbitrary vertex order is not itself an invariant.
First Filter: Counts and Degree Sequences
Worked Example: Three Carbon Skeletons with Formula C5H12
Consider three candidate carbon skeletons. Each has five carbon vertices and four single bonds.
For the straight chain, let \(V=\{1,2,3,4,5\}\) and \(E=\{12,23,34,45\}\). Its degrees are \(1,2,2,2,1\), so its degree sequence is \((2,2,2,1,1)\).
For a branched skeleton, let \(V=\{1,2,3,4,5\}\) and \(E=\{12,13,14,45\}\). Its degrees are \(3,1,1,2,1\), so its degree sequence is \((3,2,1,1,1)\).
For a four-branch skeleton, let \(V=\{1,2,3,4,5\}\) and \(E=\{12,13,14,15\}\). Its degrees are \(4,1,1,1,1\), so its degree sequence is \((4,1,1,1,1)\).
All three pass the same basic count checks: each has five vertices and four edges. In each case the sum of the degrees is \(8=2\cdot4\), as required because each edge contributes one to the degree of each endpoint. For a single-bond carbon skeleton, the number of implicit hydrogens is the sum of \(4-\deg(v)\) over its carbon vertices. The three sums are respectively \(3+2+2+2+3=12\), \(1+3+3+2+3=12\), and \(0+3+3+3+3=12\). Thus each graph has formula C5H12.
The degree sequences differ, so the three graphs are pairwise nonisomorphic. This conclusion does not depend on which vertex names were chosen: any isomorphism would have to preserve the degree sequence.
Check: each graph has four edges, and the displayed degrees sum to \(8\). The hydrogen count is \(4\cdot5-8=12\) in every case, agreeing with the direct sums above.
This example illustrates a useful screening order. First compare the numbers of atoms and bonds, then compare the counts of each atom and bond label, and then compare degree sequences. A mismatch at any stage rules out an isomorphism. Matching those values only means that more detailed tests are needed.
Equal Degree Sequences Can Still Differ
Worked Example: Two C6H14 Graphs with the Same Degree Sequence
Let \(G\) have \(V(G)=\{1,2,3,4,5,6\}\) and \(E(G)=\{12,13,14,45,56\}\). Its adjacency lists are \(1:\{2,3,4\}\), \(2:\{1\}\), \(3:\{1\}\), \(4:\{1,5\}\), \(5:\{4,6\}\), and \(6:\{5\}\). The degrees are \(3,1,1,2,2,1\), giving degree sequence \((3,2,2,1,1,1)\).
Let \(H\) have \(V(H)=\{a,b,c,d,e,f\}\) and \(E(H)=\{ab,bc,cd,de,cf\}\). Its adjacency lists are \(a:\{b\}\), \(b:\{a,c\}\), \(c:\{b,d,f\}\), \(d:\{c,e\}\), \(e:\{d\}\), and \(f:\{c\}\). Its degrees are \(1,2,3,2,1,1\), so its degree sequence is also \((3,2,2,1,1,1)\).
Both graphs have six carbon vertices and five single bonds. Their degree sums are \(3+2+2+1+1+1=10=2\cdot5\); their implicit hydrogen counts are \(24-10=14\). Both are connected trees, so neither has any cycles. These tests do not distinguish them.
Now examine the unique degree-3 vertex in each graph. In \(G\), vertex \(1\) has neighbors \(2,3,4\), whose degrees are \(1,1,2\). The multiset of neighbor degrees is therefore \(\{1,1,2\}\). In \(H\), vertex \(c\) has neighbors \(b,d,f\), whose degrees are \(2,2,1\), giving \(\{1,2,2\}\). An isomorphism would have to send the unique degree-3 vertex to the unique degree-3 vertex and preserve the degrees of all its neighbors. Since these neighbor-degree multisets differ, no such isomorphism exists.
Check: the common degree sequence and the common cycle counts did not prove isomorphism. The neighbor-degree test supplied a further invariant that separates these two graphs.
The neighbor-degree comparison is an example of refining a basic invariant: rather than recording only each vertex’s degree, record the degrees of its neighbors as well. Whenever an isomorphism maps one vertex to another, it must map their neighbor sets bijectively and preserve the degrees within those sets. Thus the multiset of neighbor degrees is preserved. This test is still only a filter; agreement does not by itself establish isomorphism.
Cycle Counts and Detailed Adjacency
Worked Example: Equal Degrees, Different Triangle Counts
Consider two six-vertex, single-bond carbon skeletons. Define \(G\) by \(V(G)=\{a,b,c,A,B,C\}\) and \(E(G)=\{ab,bc,ca,AB,BC,CA,aA,bB,cC\}\). Define \(H\) by the parts \(\{a,b,c\}\) and \(\{A,B,C\}\), with \(V(H)=\{a,b,c,A,B,C\}\) and \(E(H)=\{aA,aB,aC,bA,bB,bC,cA,cB,cC\}\).
Every vertex in either graph has degree \(3\): \(G\) has two neighbors within its triangle and one across to the other triangle, while each vertex of \(H\) is adjacent to all three vertices in the opposite part. Thus both graphs have degree sequence \((3,3,3,3,3,3)\), and both have \(9\) edges, since the degree sum is \(6\cdot3=18=2\cdot9\).
In \(G\), the vertex triples \(\{a,b,c\}\) and \(\{A,B,C\}\) each form a triangle, so \(G\) has two triangles. There are no further triangles: each edge between the two triples is one of \(aA,bB,cC\), and a triangle using vertices from both triples would need two edges between the triples incident to the same vertex; no vertex has two such edges. In \(H\), every edge crosses between the two parts. A walk around a triangle would switch parts at every edge, and after three switches it would be in the opposite part from where it started. Hence \(H\) has no triangles.
Triangle count is a cycle-count invariant, so these graphs are not isomorphic despite having the same vertex count, edge count and degree sequence. Each has six carbon vertices of degree \(3\), hence \(6\cdot(4-3)=6\) implicit hydrogens. These are valence-compatible graph examples; the graph comparison alone does not assert that either structure is a stable, isolable compound.
Check: both degree sums are \(18\), giving \(18/2=9\) edges. The triangle counts are \(2\) and \(0\), so the cycle-count test distinguishes the graphs.
When the easy invariants agree, a proposed vertex correspondence can be checked directly. In the next example, the labels differ, but the edge lists match exactly after applying the correspondence.
Worked Example: Confirming Isomorphism by a Vertex Bijection
Let \(G\) have \(V(G)=\{a,b,c,d,e\}\) and \(E(G)=\{ab,bc,cd,de\}\). Let \(H\) have \(V(H)=\{1,2,3,4,5\}\) and \(E(H)=\{13,34,42,25\}\). Define \(f(a)=1\), \(f(b)=3\), \(f(c)=4\), \(f(d)=2\), and \(f(e)=5\). These five images are distinct and exhaust \(V(H)\), so \(f\) is a bijection.
Check every edge of \(G\): \(ab\) maps to \(13\), \(bc\) maps to \(34\), \(cd\) maps to \(42\), and \(de\) maps to \(25\). These are exactly the four edges of \(H\). Both graphs have four edges, so the mapped edges account for all of \(E(H)\); no extra edge remains. All vertices have the same atom label and all edges the same bond label. Therefore \(f\) is an isomorphism.
Check: \(G\) has degree sequence \((2,2,2,1,1)\). In \(H\), the degrees of \(1,2,3,4,5\) are respectively \(1,2,2,2,1\), giving the same sorted sequence. This agrees with the explicit isomorphism.
A Practical Comparison and Common Pitfall
For candidate molecular graphs, a careful comparison can proceed in stages:
- Check that the vertex and edge counts agree, along with the counts of each atom and bond label.
- Compare the degree sequences. If they differ, the graphs are not isomorphic.
- Compare cycle counts, beginning with short cycles such as triangles, and inspect further neighborhood data if needed.
- If the tests still agree, propose a label-preserving bijection and verify that it preserves every adjacency and bond label.
Common mistake: treating matching invariants as proof of isomorphism. For the two graphs in the C6H14 example, both degree sequences are \((3,2,2,1,1,1)\). A tempting but incorrect conclusion is “the degree sequences match, so the graphs are isomorphic.” The correction is to check the actual adjacency structure: the unique degree-3 vertex has neighbor degrees \(\{1,1,2\}\) in \(G\) but \(\{1,2,2\}\) in \(H\). Since an isomorphism preserves this data, the graphs cannot be isomorphic.
There is a complementary mistake: rejecting an isomorphism because the vertex names or adjacency lists look different. In the final example, the lists use different labels, but the explicit bijection matches all four edges. Names are bookkeeping; the preserved structure is what decides the question. In molecular applications, the labels are not bookkeeping: an isomorphism must also respect which atoms and bond types are present.
Check Your Understanding
Use invariants to rule out impossible correspondences, and use explicit adjacency checks when you claim isomorphism.
- Why does a difference in degree sequence rule out an isomorphism, even when the two graphs have the same number of vertices and edges?
- For the two C6H14 graphs above, compute the degree of each neighbor of the unique degree-3 vertex and explain how this distinguishes the graphs.
- Why must an isomorphism preserve the number of triangles?
- In the last worked example, verify the images of all four edges under the stated bijection.
- Can two graphs with the same vertex count, edge count, degree sequence and triangle count still fail to be isomorphic? Explain why agreement on these tests alone is not a proof.