Choosing Vertices and Edges
A graph can be made smaller in two different ways: by removing vertices, or by removing edges while keeping the vertices. The formal definition of a subgraph records both choices. It also makes an important restriction explicit: an edge can be included only if both its endpoints are included. On the other hand, keeping both endpoints does not require keeping the edge between them.
All graphs in this tutorial are finite and simple. Thus an edge \(uv\) joins two distinct vertices, and there is at most one edge between any pair of vertices. For a graph \(G\), write \(V(G)\) for its vertex set and \(E(G)\) for its edge set. Its order is \(|V(G)|\), and its size is \(|E(G)|\).
The endpoint condition is essential. For example, if \(V(H)=\{1,2,3\}\), then an edge \(14\) cannot belong to \(E(H)\), even if \(14\in E(G)\), because vertex \(4\) is not in \(V(H)\). By contrast, if \(12\in E(G)\) and both \(1\) and \(2\) belong to \(V(H)\), the edge \(12\) is available to include but is not compulsory.
A spanning subgraph keeps every vertex, including any vertices that become isolated after edges are removed. It may keep all, some, or none of the edges of \(G\). The graph \(G\) itself is a spanning subgraph of \(G\), though it is not a proper subgraph. The graph with vertex set \(V(G)\) and no edges is also a spanning subgraph.
How Subgraphs Are Formed
For a vertex \(v\), the notation \(G-v\) means remove \(v\) and all edges incident with \(v\). For an edge \(e\), \(G-e\) means remove \(e\) while retaining all vertices. These operations give a useful way to describe any subgraph: first remove the vertices that are not wanted, then remove any remaining edges that are not wanted.
Proof. Suppose first that \(H\) is a subgraph of \(G\). Delete from \(G\) every vertex in \(V(G)\setminus V(H)\), together with its incident edges. The remaining vertices are exactly \(V(H)\). Every edge of \(E(H)\) remains, because its endpoints are in \(V(H)\). Some other edges may remain as well, but each is an edge of \(G\) with both endpoints in \(V(H)\). Delete all those remaining edges that are not in \(E(H)\). The resulting graph has vertex set \(V(H)\) and edge set \(E(H)\), so it is \(H\). Conversely, deleting vertices and edges from \(G\) leaves only vertices from \(V(G)\) and edges from \(E(G)\); any edge left in the graph has both endpoints among the vertices left. The result therefore satisfies the definition of a subgraph. If \(H\) is spanning, no vertices need to be deleted, so only edge deletions are needed. Conversely, deleting edges only leaves the vertex set unchanged, so the resulting subgraph is spanning. \(\square\)
Two immediate checks follow from the definition. If \(H\) is a subgraph of \(G\), then \(|V(H)|\le |V(G)|\) and \(|E(H)|\le |E(G)|\). Also, for any \(v\in V(H)\), every neighbor of \(v\) in \(H\) is a neighbor of \(v\) in \(G\), so \(\deg_H(v)\le \deg_G(v)\).
Proof. Fix \(v\in V(H)\). Each edge of \(H\) incident with \(v\) is also an edge of \(G\) incident with \(v\), since \(E(H)\subseteq E(G)\). Thus the set of edges incident with \(v\) in \(H\) is a subset of the set of edges incident with \(v\) in \(G\). The degrees count these sets of incident edges, so \(\deg_H(v)\le \deg_G(v)\). This also covers degree zero: if \(v\) has no incident edges in \(H\), then \(\deg_H(v)=0\le\deg_G(v)\). \(\square\)
Worked Examples
Worked Example: A Subgraph with Fewer Vertices
Let \(G\) have vertex set \(V(G)=\{1,2,3,4,5\}\) and edge set \(E(G)=\{12,13,23,24,34,45\}\). Consider the graph \(H\) with \(V(H)=\{1,2,3,4\}\) and \(E(H)=\{12,23,24\}\). Check whether \(H\) is a subgraph of \(G\).
First, \(\{1,2,3,4\}\subseteq\{1,2,3,4,5\}\). Second, each chosen edge \(12,23,24\) belongs to \(E(G)\). Each has both endpoints in \(V(H)\). Therefore \(H\) is a subgraph of \(G\). It is not spanning, because vertex \(5\) is not in \(V(H)\), and it is proper because its vertex set differs from that of \(G\).
The omitted edges illustrate both parts of the edge rule. Edge \(45\) cannot be in \(H\), because endpoint \(5\) was not retained. Edges \(13\) and \(34\) could have been included, since their endpoints are retained, but the definition does not require them to be included.
Check: \(H\) has order \(4\) and size \(3\). Its degrees are \(\deg_H(1)=1\), \(\deg_H(2)=3\), \(\deg_H(3)=1\), and \(\deg_H(4)=1\). In \(G\), the corresponding degrees are \(2,3,3,3\), respectively. Each degree in \(H\) is no greater than the corresponding degree in \(G\), as the proposition requires.
Worked Example: A Spanning Subgraph with Isolated Vertices
Use the same graph \(G\), with \(V(G)=\{1,2,3,4,5\}\) and \(E(G)=\{12,13,23,24,34,45\}\). Let \(S\) have \(V(S)=\{1,2,3,4,5\}\) and \(E(S)=\{12,45\}\).
The vertex sets are equal, so \(S\) is spanning if it is a subgraph. Both selected edges, \(12\) and \(45\), belong to \(E(G)\) and have endpoints in \(V(S)\). Thus \(S\) is indeed a spanning subgraph. It is proper because, for example, \(13\in E(G)\) but \(13\notin E(S)\).
Vertices \(3\) and \(4\) are both retained. In \(S\), vertex \(3\) is isolated, meaning it has degree zero; vertex \(4\) is not isolated because edge \(45\) remains. Removing edges does not remove their endpoints. The degrees in \(S\) are \(\deg_S(1)=1\), \(\deg_S(2)=1\), \(\deg_S(3)=0\), \(\deg_S(4)=1\), and \(\deg_S(5)=1\).
Check: \(S\) has the same order as \(G\), namely \(5\), and its size is \(2\), compared with size \(6\) for \(G\). The degree sum in \(S\) is \(1+1+0+1+1=4\), which is twice its two edges. This independently checks the listed degrees and edge count.
Worked Example: Same Vertices, Different Edge Choices
Let \(G\) have vertex set \(V(G)=\{a,b,c,d,e\}\) and edge set \(E(G)=\{ab,ac,bc,cd,de,ce\}\). Set \(W=\{b,c,d,e\}\). Consider \(H_1\) with \(V(H_1)=W\) and \(E(H_1)=\{bc,cd,de\}\), and \(H_2\) with \(V(H_2)=W\) and \(E(H_2)=\{bc,cd,de,ce\}\).
For each graph, the chosen vertices belong to \(V(G)\). Every edge listed for \(H_1\) or \(H_2\) is in \(E(G)\) and has both endpoints in \(W\). Hence both are subgraphs of \(G\), and neither is spanning because \(a\notin W\). The edge \(ac\) is unavailable to either subgraph because it uses \(a\). Edge \(ce\), however, is available: it is omitted from \(H_1\) and included in \(H_2\). Thus the same vertex set can give different subgraphs.
Check: \(H_1\) has order \(4\) and size \(3\); its degrees at \(b,c,d,e\) are \(1,2,2,1\). Their sum is \(6=2\cdot3\). The graph \(H_2\) has order \(4\) and size \(4\); its degrees at \(b,c,d,e\) are \(1,3,2,2\). Their sum is \(8=2\cdot4\). Adding \(ce\) increases the degrees of \(c\) and \(e\) by one and leaves the other degrees unchanged.
Counting Spanning Subgraphs
If \(G\) has \(m\) edges, each spanning subgraph is determined by deciding, independently for each edge, whether to retain it. Therefore there are \(2^m\) spanning subgraphs, counting \(G\) itself and the spanning graph with no edges.
Proof. A spanning subgraph must have vertex set \(V(G)\). Its edge set can be any subset of \(E(G)\): every such subset gives a spanning subgraph, and two different subsets give different edge sets and hence different subgraphs. A set with \(m\) elements has \(2^m\) subsets, since each of its \(m\) elements has two choices, included or not included. This includes \(m=0\), when the only subset is the empty edge set and \(2^0=1\). \(\square\)
For the graph in the first two examples, \(m=6\), so the number of spanning subgraphs is \(2^6=64\). This count includes the original graph and the spanning subgraph with no edges. It does not count subgraphs with smaller vertex sets.
Common Mistakes and Checks
Mistake: treating every edge between retained vertices as compulsory. In the first example, one might wrongly insist that \(13\) and \(34\) must be in \(H\), because all their endpoints are in \(V(H)\). That would give the edge set \(\{12,13,23,24,34\}\), not the specified \(E(H)=\{12,23,24\}\). The correction is that a subgraph may omit any edge of \(G\); the definition requires only that each edge it does include belongs to \(G\) and has retained endpoints.
Mistake: retaining an edge while deleting one of its endpoints. With \(V(H)=\{1,2,3,4\}\), adding \(45\) to the edge set would make the proposed graph fail the endpoint condition. To include \(45\), vertex \(5\) must also be included. A reliable check is to inspect every selected edge after choosing the vertex set.
Mistake: assuming a spanning subgraph must be connected or must retain a particular number of edges. The definition requires exactly that all vertices are retained and that the selected edges come from \(G\) with their endpoints retained. It imposes no connectivity condition and no fixed edge count. Isolated vertices and disconnected spanning subgraphs are allowed.
When checking a proposed subgraph \(H\) of \(G\), use the following order: compare the vertex sets; compare the edge sets; then check the endpoints of every edge in \(E(H)\). If the vertex sets are equal, \(H\) is spanning. If not, it is not spanning, regardless of how many edges it retains.
Check Your Understanding
For each question, write out the vertex and edge conditions you use.
- Let \(G\) have \(V(G)=\{1,2,3,4\}\) and \(E(G)=\{12,13,23,34\}\). Is the graph with vertex set \(\{1,2,3\}\) and edge set \(\{12,13\}\) a subgraph? Is it spanning?
- In the same \(G\), can a graph with vertex set \(\{1,2,4\}\) and edge set \(\{12,23\}\) be a subgraph? Identify the exact condition it violates, if any.
- Give two distinct spanning subgraphs of a graph with edge set \(\{12,13\}\), and state their vertex and edge sets.
- Explain why retaining all vertices but no edges always gives a spanning subgraph.
- A graph \(G\) has \(4\) edges. How many spanning subgraphs does it have? Explain the choices being counted.