Comparing Subgraphs by Worked Examples

Comparing Graphs from Their Lists

When two graphs are given by vertex and edge lists, deciding whether one is a subgraph of the other is a finite comparison: check the vertices, then check the edges. To decide whether it is an induced subgraph, one more question matters: are there any edges in the larger graph between selected vertices that the smaller graph has left out? This distinction is useful whenever a graph is formed by keeping some of the original vertices, with or without all the edges among them.

Throughout, graphs are finite and simple. An edge \(uv\) denotes the unordered pair \(\{u,v\}\), and an edge list such as \(12,23\) is a set of edges. We compare graphs using their displayed vertex names: a vertex named \(1\) in one graph is the same vertex as \(1\) in the other only when the lists establish that fact. Whether graphs with different labels can be matched by a relabeling is a question of graph isomorphism, not the comparison made here.

For a vertex set \(S\subseteq V(G)\), the induced subgraph on \(S\), written \(G[S]\), has vertex set \(S\) and edge set consisting of every edge of \(G\) with both endpoints in \(S\). Thus selecting vertices determines \(G[S]\) uniquely. An ordinary subgraph on the same selected vertices can have fewer edges than \(G[S]\). In the special case \(S=\varnothing\), the induced subgraph has no vertices and no edges; the definitions apply without change.

A Direct Test

For explicit lists, use two tests in order. First compare the vertex sets: every vertex listed for \(H\) must occur in \(G\). Next compare the edge sets: every edge listed for \(H\) must occur in \(G\), with both its endpoints among the vertices of \(H\). These conditions are exactly the definition of an ordinary subgraph. For an induced subgraph, additionally list all the edges of \(G\) whose endpoints are both in \(V(H)\) and check that this list agrees exactly with \(E(H)\).

Proof. Suppose first that \(H\) is induced in \(G\). By definition, \(V(H)\subseteq V(G)\), and \(E(H)\) contains exactly the edges of \(G\) whose endpoints both belong to \(V(H)\). Therefore, for every distinct \(u,v\in V(H)\), the edge \(uv\) belongs to \(H\) precisely when it belongs to \(G\). Conversely, suppose the vertex inclusion holds and the stated equivalence holds for every pair of distinct vertices in \(V(H)\). Since the graphs are simple, all edges have two distinct endpoints. The equivalence therefore says that \(E(H)\) consists of all and only the edges of \(G\) with both endpoints in \(V(H)\). This is precisely the definition of \(H\) being induced in \(G\). \(\square\)

This test highlights the difference between the two questions. For a subgraph, an edge of \(H\) must be present in \(G\), but \(H\) may omit other edges of \(G\). For an induced subgraph, it may not omit any edge of \(G\) between its chosen vertices.

When Vertex Selection Gives an Induced Subgraph

Once a vertex set \(S\) has been selected, there is no further choice in forming the induced subgraph: retain every host edge whose endpoints both lie in \(S\). This provides a useful way to organize comparisons. First compute \(G[S]\); then compare the candidate edge set with the edge set of \(G[S]\). Equality means the candidate is induced, while a proper subset means it is a non-induced subgraph on those vertices, provided its listed edges are indeed host edges.

Proof. Assume \(H\) is a subgraph, so its vertices are in \(G\) and each edge of \(H\) is an edge of \(G\) with endpoints in \(V(H)\). If \(H\) is induced, its definition says that it contains every host edge with both endpoints in \(V(H)\); the subgraph condition already ensures it contains no other edges. Therefore \(E(H)=E(G[V(H)])\). Conversely, if the edge sets are equal, then \(H\) contains exactly the edges of \(G\) with both endpoints in \(V(H)\). Together with \(V(H)\subseteq V(G)\), this is the definition of an induced subgraph. \(\square\)

Failures of the Subgraph Test

A candidate can fail to be a subgraph in either of the two basic checks: it may list a vertex absent from the host, or it may list an edge absent from the host. An extra host edge between selected vertices does not cause failure as an ordinary subgraph; it causes failure only for the induced test. Keeping these cases separate prevents a common mix-up.

A Reliable Comparison Checklist

For a pair of listed graphs, record the results in a small table rather than relying on a visual impression. When the names are the same, direct membership checks are enough; when they differ, this test does not permit relabeling. The edge test for inducedness must use the host graph, not the candidate’s list alone.

Common mistake. A frequent incorrect calculation is: “The vertices of \(H\) are in \(G\), so \(H\) is induced.” Vertex inclusion is necessary, but it does not check any edges. In the first worked example, \(V_H\subseteq V(G)\) and \(E_H\subseteq E(G)\), yet \(H\) is not induced because the host edges \(13\) and \(24\) between selected vertices are missing from \(H\). The correction is to compute \(G[V(H)]\) and compare its edge set with \(E(H)\), not to stop after checking the vertices.

Another error is to reject an ordinary subgraph merely because the host has extra edges between selected vertices. That reasoning applies only to induced subgraphs. In the first example, \(H\) is an ordinary subgraph precisely because its own edges all occur in \(G\); the extra host edges explain why it is not induced, not why it fails to be a subgraph.