The same graph can be drawn in many ways, with different labels. When are two graphs "really the same"? The answer uses a bijection between their vertex sets, and the named graphs from special graphs give good test cases.
Idea clave
Graphs $G$ and $H$ are isomorphic when there is a bijection $f : V(G) \to V(H)$ such that $u$ and $v$ are joined in $G$ exactly when $f(u)$ and $f(v)$ are joined in $H$. Properties preserved by every isomorphism are invariants: the number of vertices and edges, the degree sequence, connectedness, the number of triangles, the lengths of cycles. Different invariants prove two graphs are not isomorphic; matching invariants do not prove they are.
Por qué funciona
An isomorphism is a relabeling: rename each vertex $u$ of $G$ as $f(u)$, and the edge set becomes exactly the edge set of $H$. Anything defined only from vertices and edges, without looking at the names or the drawing, survives a relabeling. That is why invariants can rule isomorphism out. But many different graphs share all the simple invariants, so to show two graphs are isomorphic you have to produce the bijection.
Worked examples
Ejemplo resuelto: An invariant that differs
$G$ has edges $AB, BC, CD, DA, AC$ and $H$ has edges $12, 23, 34, 41, 13, 24$. Are they isomorphic?
- $G$ has $5$ edges and $H$ has $6$.
- An isomorphism maps edges to edges one-to-one, so the counts would have to match. Not isomorphic.
Respuesta: No
Ejemplo resuelto: Same degrees, still different
Is $C_{6}$ isomorphic to the graph made of two separate triangles?
- Both have $6$ vertices, $6$ edges, and every degree $2$.
- But $C_{6}$ is connected and has no triangles, while the other graph has two components and two triangles.
- Not isomorphic: connectedness and triangle counts are invariants.
Respuesta: No
Ejemplo resuelto: Building an isomorphism
$G$ is the cycle $A - B - C - D - E - A$. $H$ has edges $13, 35, 52, 24, 41$. Find an isomorphism.
- $H$ is also a cycle of length $5$: follow it, $1 \to 3 \to 5 \to 2 \to 4 \to 1$.
- Send the cycles to each other in order: $A \mapsto 1$, $B \mapsto 3$, $C \mapsto 5$, $D \mapsto 2$, $E \mapsto 4$.
- Check every edge: $AB \mapsto 13$, $BC \mapsto 35$, $CD \mapsto 52$, $DE \mapsto 24$, $EA \mapsto 41$. All are edges of $H$.
Respuesta: $A \mapsto 1, B \mapsto 3, C \mapsto 5, D \mapsto 2, E \mapsto 4$
Error común
Deciding "isomorphic" because the degree sequences match. Matching invariants are necessary, not sufficient; $C_{6}$ and two triangles share their degree sequence. Check: to prove "isomorphic," write the bijection and verify every edge; to prove "not isomorphic," name an invariant that differs.