Choosing Vertices Determines the Edges
When a problem asks for the graph “on” a chosen set of vertices, the edge set is not an additional choice. The selected vertices determine it: retain exactly those original edges whose two endpoints were selected. This operation is called taking an induced subgraph.
Throughout, graphs are finite and simple: they have no loops or multiple edges. If \(G=(V,E)\) is a graph and \(S\subseteq V\), then the induced subgraph on \(S\) keeps the vertices in \(S\) and checks each edge of \(G\) to see whether both endpoints belong to \(S\). In particular, selecting vertices does not mean selecting only some of the edges between them.
The condition on the edge set has two parts: an edge must already be in \(G\), and both its endpoints must be selected. Thus an edge from a selected vertex to an unselected vertex disappears, while an edge between two selected vertices must remain. If \(S=\varnothing\), then \(G[S]\) has no vertices and no edges. If \(S\) contains one vertex, then \(G[S]\) has that vertex and no edges, because the graph is simple.
This is more restrictive than an ordinary subgraph. A subgraph with vertex set \(S\) may omit some of the edges of \(G\) that have both endpoints in \(S\). The induced subgraph cannot omit any of them. Equivalently, \(G[S]\) is the subgraph on \(S\) with as many edges as the original graph permits.
Constructing an Induced Subgraph
A reliable method is to list the selected vertices first, then inspect the original edge set one edge at a time. Keep an edge exactly when both endpoints are in the selected set. This procedure avoids a common error: recording only edges that were convenient to notice or that appear to form a desired pattern.
Record \(S\subseteq V(G)\); these, and only these, are the vertices of \(G[S]\).
For each \(uv\in E(G)\), include it if and only if \(u\in S\) and \(v\in S\).
Confirm that every listed edge is an original edge with both endpoints selected, and that no such original edge was left out.
Worked Example: Selecting Four Vertices
Let \(G=(V,E)\), where \(V=\{1,2,3,4,5,6\}\) and \(E=\{12,13,24,25,34,36,45,56\}\). Find \(G[S]\) for \(S=\{1,2,3,4\}\).
The selected vertices are exactly \(1,2,3,4\). Test the original edges in order. The edge \(12\) has both endpoints selected, so retain it. The edge \(13\) has both endpoints selected, so retain it. The edge \(24\) has both endpoints selected, so retain it. The edge \(25\) is excluded because \(5\notin S\). The edge \(34\) has both endpoints selected, so retain it. The edge \(36\) is excluded because \(6\notin S\). The edge \(45\) is excluded because \(5\notin S\). The edge \(56\) is excluded because neither endpoint is selected.
Therefore \(V(G[S])=\{1,2,3,4\}\) and \(E(G[S])=\{12,13,24,34\}\).
Check: Each of \(12,13,24,34\) is in \(E\), and both its endpoints are in \(S\). The other original edges have at least one endpoint outside \(S\), so none of them belongs to \(G[S]\). Thus the listed edge set contains all and only the required edges.
The edge test can also be expressed using neighborhoods. The neighborhood \(N_G(v)\) of a vertex \(v\) is the set of vertices adjacent to \(v\) in \(G\). If \(v\in S\), then its neighbors in the induced subgraph are precisely the selected original neighbors: $$ N_{G[S]}(v)=N_G(v)\cap S. $$ Consequently, its degree in the induced subgraph is $$ \deg_{G[S]}(v)=|N_G(v)\cap S|. $$ This degree can be smaller than its degree in \(G\), because neighbors outside \(S\) have been removed.
Proof. Let \(w\) be any vertex. By definition, \(w\in N_{G[S]}(v)\) exactly when \(w\in S\) and \(vw\in E(G[S])\). The definition of the induced edge set says \(vw\in E(G[S])\) exactly when \(vw\in E\), since \(v,w\in S\). Thus \(w\in N_{G[S]}(v)\) exactly when \(w\in S\) and \(w\in N_G(v)\), which is the condition \(w\in N_G(v)\cap S\). The neighborhood sets are therefore equal. The degree is the number of neighbors, so taking the size of both sides gives the degree formula. \(\square\)
Worked Example: Degrees After Vertex Selection
Let \(G=(V,E)\), where \(V=\{a,b,c,d,e\}\) and \(E=\{ab,ac,ad,bc,ce,de\}\). Take \(S=\{a,b,c,d\}\). Determine the induced edge set and the degrees in \(G[S]\).
Check each original edge. The endpoints of \(ab\), \(ac\), \(ad\), and \(bc\) all belong to \(S\), so retain those four edges. The edge \(ce\) is excluded because \(e\notin S\), and \(de\) is excluded for the same reason. Thus \(E(G[S])=\{ab,ac,ad,bc\}\).
Now count the neighbors within \(S\). Vertex \(a\) is adjacent in \(G[S]\) to \(b,c,d\), so \(\deg_{G[S]}(a)=3\). Vertex \(b\) is adjacent to \(a,c\), so \(\deg_{G[S]}(b)=2\). Vertex \(c\) is adjacent to \(a,b\), so \(\deg_{G[S]}(c)=2\). Vertex \(d\) is adjacent to \(a\), so \(\deg_{G[S]}(d)=1\).
Check: The degree sum is \(3+2+2+1=8\), and the edge set has four edges, so twice its size is \(2\cdot4=8\). The degree sum agrees with the handshake count. In the original graph, \(c\) had the additional neighbor \(e\); since \(e\notin S\), that edge contributes nothing to its degree in \(G[S]\).
What Makes the Induced Subgraph Unique?
Once \(S\) is fixed, there is only one induced subgraph on \(S\): every possible edge is decided by whether it belongs to \(G\) and has both endpoints in \(S\). The next characterization makes the difference from a general subgraph exact.
Proof. First suppose \(H=G[S]\). If \(uv\in E(G)\) and \(u,v\in S\), then the definition of \(G[S]\) includes \(uv\) in \(E(G[S])\). Since \(H=G[S]\), it follows that \(uv\in E(H)\).
Conversely, suppose every edge of \(G\) with both endpoints in \(S\) belongs to \(H\). Since \(H\) is a subgraph of \(G\) with vertex set \(S\), each edge of \(H\) is an edge of \(G\) with both endpoints in \(S\). This gives \(E(H)\subseteq E(G[S])\). The stated condition gives \(E(G[S])\subseteq E(H)\). Hence the two edge sets are equal, and their vertex sets are both \(S\), so \(H=G[S]\). \(\square\)
The condition is useful as a direct test: to show a subgraph on \(S\) is induced, check that it has not omitted any original edge whose endpoints both lie in \(S\). If even one such edge is missing, the subgraph is not induced.
Worked Example: An Edge That Cannot Be Omitted
Let \(G=(V,E)\), where \(V=\{1,2,3,4\}\) and \(E=\{12,13,23,34\}\). Choose \(S=\{1,2,3\}\). A proposed graph \(H\) has vertex set \(S\) and edge set \(\{12,13\}\). Is \(H\) the induced subgraph on \(S\)?
Inspect the original edges. The edges \(12\), \(13\), and \(23\) all have both endpoints in \(S\), so all three must occur in \(G[S]\). The edge \(34\) does not qualify because \(4\notin S\). Therefore \(E(G[S])=\{12,13,23\}\), while \(E(H)=\{12,13\}\).
The proposed \(H\) omits \(23\), even though \(23\in E(G)\) and both endpoints are in \(S\). Hence \(H\neq G[S]\). It is a subgraph on \(S\), but it is not the induced subgraph.
Check: Adding the omitted edge gives \(\{12,13,23\}\), exactly the set obtained by testing every edge of \(G\). The edge \(34\) remains excluded because one endpoint is outside \(S\).
Nested Vertex Selections
Induced subgraphs can be selected in stages. If \(T\subseteq S\subseteq V(G)\), first taking \(G[S]\) and then selecting \(T\) produces the same graph as selecting \(T\) directly from \(G\). The reason is that an edge survives either process exactly when it was in \(G\) and both endpoints belong to \(T\).
Proof. The vertex set of \((G[S])[T]\) is \(T\), as is the vertex set of \(G[T]\). For any pair of vertices \(u,v\in T\), the edge \(uv\) belongs to \((G[S])[T]\) exactly when it belongs to \(G[S]\). Because \(u,v\in S\), the definition of \(G[S]\) says this happens exactly when \(uv\in E(G)\). That is precisely the condition for \(uv\in E(G[T])\), since \(u,v\in T\). Thus the two graphs have the same vertices and the same edges. The reasoning also applies when \(T=\varnothing\), because both graphs then have empty vertex and edge sets. \(\square\)
This property is useful when a selection is refined step by step. It also provides a check on calculations: removing vertices in stages cannot create an edge or restore one that was absent in the original graph.
Common Pitfall: Treating the Edge Set as Optional
A frequent mistake is to select the right vertices but keep only a convenient subset of the edges between them. For instance, in the previous example, one might report \(\{12,13\}\) because those edges seem to describe the selected vertices. That calculation is wrong for an induced subgraph: it overlooks the original edge \(23\), whose endpoints were both selected. The correction is to test every original edge against the selected set.
There is a second, opposite error: keeping an edge just because one endpoint was selected. An edge \(uv\) remains only when both \(u\in S\) and \(v\in S\). An edge from a selected vertex to an unselected vertex is not part of \(G[S]\).
| Original edge \(uv\) | Endpoint membership | In \(G[S]\)? |
|---|---|---|
| \(uv\in E(G)\) | \(u\in S,\ v\in S\) | Yes |
| \(uv\in E(G)\) | Exactly one of \(u,v\) is in \(S\) | No |
| \(uv\in E(G)\) | \(u\notin S,\ v\notin S\) | No |
| \(uv\notin E(G)\) | \(u\in S,\ v\in S\) | No |
The last row matters: selection does not add edges. The induced subgraph preserves exactly the edges already present between selected vertices, not every possible edge between them.
Check Your Understanding
For each question, use the endpoint test in the definition and state the resulting edge set explicitly.
- Let \(V(G)=\{1,2,3,4,5\}\), \(E(G)=\{12,14,23,24,35,45\}\), and \(S=\{1,2,4,5\}\). Find \(V(G[S])\) and \(E(G[S])\).
- For the graph in Question 1, find \(\deg_{G[S]}(4)\) using its selected neighbors.
- Let \(G\) have \(V(G)=\{a,b,c,d\}\) and \(E(G)=\{ab,bc,cd,ad\}\). Is the graph \(H\) with vertex set \(\{a,b,c\}\) and edge set \(\{ab,bc\}\) induced in \(G\)? Explain.
- Suppose \(T\subseteq S\subseteq V(G)\). Explain why an edge belongs to \((G[S])[T]\) exactly when it belongs to \(G[T]\).
- What is the induced subgraph on the empty vertex set? What is the induced subgraph on a single selected vertex in a simple graph?