Isomorphism and its limits
A different drawing is not a different graph. Verify the connection structure under a bijection
- Necessary invariants Isomorphism preserves vertex count, edge count, degrees, loops, parallel multiplicity and connectedness
- Bijection Assign every vertex of one graph a different vertex of the other, using all vertices
- All connections Every edge and non-edge must correspond. For multigraphs, also preserve loop and parallel-edge multiplicity
- Limits of counts Equal counts and degree sequences are necessary, not sufficient. A valid complete correspondence is the positive proof
Worked example
Explain why a six-cycle and two disjoint triangles are not isomorphic, although their counts and degrees agree
\[\begin{gathered}c(C_6)=1\\c(C_3\cup C_3)=2\end{gathered}\]
- \(\displaystyle |V|=6,\quad |E|=6\)These counts agree for both graphs
- \(\displaystyle (2,2,2,2,2,2)\)Both degree sequences agree
- \(\displaystyle c(C_6)=1,\quad c(C_3\cup C_3)=2\)Their component counts differ, and an isomorphism preserves paths and therefore components
Common mistakes
Accepting degree sequence alone
✕The same degree sequence proves isomorphism✓Equal degree sequences still need a full correspondence check
A six-cycle and two triangles supply a counterexampleRejecting a new layout
✕Different vertex positions mean different graphs✓Positions may change while all endpoint connections are preserved
Inspect edges, not the appearance of the drawingGiving a non-bijective mapping
✕Two source vertices may map to the same target✓An isomorphism uses a bijection
Vertex identities must remain distinct and every target vertex is usedDifficulty levels
introCompare a verdict and reason for small graphs
standardSelect an isomorphic candidate using connections, not counts alone
challengeRetain the accepted looped multigraph comparison. This remains supplied-candidate recognition, not constructed correspondence
Questions about this topic
Can an isomorphism change vertex labels?+
Yes. It is a relabelling by a bijection that preserves every connection
Does the practice grade my own mapping?+
No. It grades counts and supplied verdicts/candidates. The written mapping task and full model are separate and ungraded
Must a loop be preserved?+
Yes. A loop must map to a loop at the corresponding vertex, and parallel-edge multiplicities must also match
Can I use a calculator?+
No. This topic is practised without a calculator
Which year level and chapter is this?+
Year 11, VCE Units 1 & 2, Specialist Mathematics, chapter 2: Graph theory
In this chapter
Count the vertices, edges and loops of a graphRepresent a network in a matrixIdentify the network a connection matrix describesDegrees, the degree sum, and even and odd vertices2B Graph families and structure: Graph types, subgraphs, connection models and method selectionConnected graphs and bridgesIdentify isomorphic graphsTrees and spanning treesGraph families and tree conditionsPlanar graphs and drawings in planar formFaces and Euler's formula2C Planarity and graph proofs: Graph types, subgraphs, connection models and method selectionClassify a route: walk, trail, path, circuit or cycleEulerian trails and circuits: existence and identificationHamiltonian paths and cycles