Common Mistakes With Subgraphs and Isomorphism

Why These Checks Matter

Subgraph and isomorphism questions can look straightforward: choose some vertices, copy some edges, or match the labels of one graph to another. Errors often enter when an edge is silently omitted, when a relabeling is checked only on a few edges, or when matching numerical data is treated as a complete description of a graph. The reliable approach is to state exactly what the chosen vertex set forces, and to test a proposed isomorphism against all pairs of vertices.

All graphs in this tutorial are finite and simple. Thus an edge joins two distinct vertices, and there is at most one edge between any pair. If \(G=(V,E)\), a subgraph \(H\) of \(G\) has \(V(H)\subseteq V\) and \(E(H)\subseteq E\), with every edge in \(E(H)\) having both endpoints in \(V(H)\). An induced subgraph has a stricter edge rule.

So the vertex set determines the edge set of an induced subgraph. For an ordinary subgraph, the vertex set alone does not determine which eligible edges are retained. This difference is the source of one frequent mistake.

Omitted Edges in Induced Subgraphs

Proof. By definition, any induced subgraph on \(S\) must have vertex set \(S\) and must include every edge of \(G\) with both endpoints in \(S\). It cannot include an edge not in \(G\), and it cannot include an edge incident to a vertex outside \(S\). These requirements determine its entire edge set as \(\{uv\in E(G):u\in S,\ v\in S\}\). Hence there is exactly one such graph. \(\square\)

A useful correction when an edge list seems uncertain is to inspect every edge of the original graph in turn: retain it if and only if both endpoints are in the selected set. Do not decide which edges to keep by looking only at the shape you hope to obtain.

Relabeling Is Not the Same as Changing the Graph

The “if and only if” is essential. An isomorphism preserves edges and nonedges: it does not just send some edges of \(G\) to edges of \(H\). Vertex names may change, but the adjacency pattern must remain exactly the same.

A partial check can fail. For example, the identity-style assignment \(1\mapsto a,\ 2\mapsto b,\ 3\mapsto c,\ 4\mapsto d\) is a bijection, but it sends the edge \(12\) to \(ab\), which is not an edge of \(H\). A bijection alone is not enough.

Proof. Fix any vertex \(u\in V(G)\). The definition of isomorphism says that each vertex \(v\ne u\) is adjacent to \(u\) exactly when \(f(v)\) is adjacent to \(f(u)\). Because \(f\) is a bijection, it gives a one-to-one correspondence between the neighbors of \(u\) and the neighbors of \(f(u)\). Therefore \(\deg_G(u)=\deg_H(f(u))\). As \(f\) maps every vertex of \(G\) to exactly one vertex of \(H\), the degree lists, including repetitions, agree. \(\square\)

This proposition provides a useful necessary check: different degree multisets rule out isomorphism. Matching degree multisets, however, do not guarantee isomorphism.

Why Matching Invariants Do Not Prove Isomorphism

A matching is a set of edges no two of which share an endpoint. The matching number \(\nu(G)\) is the largest size of a matching in \(G\). It records one feature of a graph, not the entire adjacency pattern.

Proof. Suppose \(f\) is an isomorphism from \(G\) to \(H\). If \(M\) is a matching in \(G\), map each edge \(uv\in M\) to the edge \(f(u)f(v)\) of \(H\). These image edges are pairwise disjoint: if two shared an endpoint, the injectivity of \(f\) would imply that the original edges shared an endpoint. Thus the image is a matching in \(H\) of size \(|M|\). In particular, a maximum matching in \(G\) shows \(\nu(H)\ge\nu(G)\). Applying the same argument to the inverse bijection \(f^{-1}\) gives \(\nu(G)\ge\nu(H)\), so \(\nu(G)=\nu(H)\). \(\square\)

This result says that equal matching numbers are required for isomorphic graphs; it does not say that equal matching numbers are enough. The distinction between a necessary condition and a sufficient condition is central to using invariants correctly.

Incomplete Isomorphism Checks

Degree multisets are not a complete test either. Two graphs may pass that check and still have different structures. One should therefore treat a matching invariant as a quick way to rule out isomorphism when it differs, not as proof when it agrees.

The same reasoning underlies the checks used throughout this topic: any property preserved by an isomorphism can disprove isomorphism when its values differ. But agreement on one or several such properties generally does not establish isomorphism unless a separate theorem says that those properties are sufficient for the particular graph family under consideration.

A Reliable Checklist and Common Pitfall

When working with a proposed subgraph or isomorphism, use a sequence of explicit checks:

1. For a subgraph, confirm that every selected edge is an edge of the original graph and has both endpoints among the selected vertices.
2. For an induced subgraph on \(S\), inspect every original edge and include it exactly when both endpoints lie in \(S\).
3. For an isomorphism, first check that the proposed vertex map is a bijection, then verify adjacency and nonadjacency for every pair.
4. For a quick comparison of graphs, use invariants such as degree multisets or matching numbers to rule out isomorphism when they differ. Do not conclude isomorphism merely because they agree.

Common mistake: In the first worked example, one might select \(S=\{1,2,3,4\}\) and write \(E=\{12,23,34\}\), claiming this is \(G[S]\). That calculation keeps a path-shaped subset of the edges, but it omits \(13\) and \(24\). Since both omitted edges belong to \(G\) and have both endpoints in \(S\), the proposed graph is not induced. The correction is to test every edge of \(G\) against \(S\), which gives \(E(G[S])=\{12,13,23,24,34\}\).

Likewise, checking only that a proposed bijection preserves the listed edges is incomplete: it may send a nonedge to an edge. And matching numbers, degree lists, and edge counts are useful filters, not automatic certificates of isomorphism. Keeping these distinctions clear prevents a small arithmetic or bookkeeping shortcut from changing the graph being studied.