edge deletions and spanning subgraphs

389 Views Asked by At

The following is from Graphs and Digraphs 6th Edition by Chartrand, Lesniak and Zhang:

For a vertex $v$ and an edge $e$ in a nonempty graph $G = (V, E)$, the subgraph $G-v$, obtained by deleting $v$ from $G$, is the induced subgraph $G[V-\{v\}]$ of $G$ and the subgraph $G-e$, obtained by deleting $e$ from G, is the spanning subgraph of $G$ with edge set $E-\{e\}$. More generally, for a propert subset $U$ of $V$, the graph $G-U$ is the induced subgraph $G[V-U]$ of $G$. For a subset $X$ of $E$, the graph $G-X$ is the spanning subgraph of $G$ with edge set $E-X$.

( The bold applied to the two instances of the word "spanning" is due to me.)

Earlier on the terms subgraph, spanning subgraph, edge-induced subgraph, etc. were defined. In particular:

(In my own words) $H$ is a spanning subgraph of $G$ if they have the same vertex set and the edge set of $H$ is a subset of the edge set of $G$. And (quoting the text again):

For a nonempty set $X$ of edges of a graph $G$, the subgraph $G[X]$ induced by $X$ has $X$ as its edge set and a vertex $v$ belongs to $G[X]$ if $v$ is incident with at least one edge in $X$.

It appears to me that the last clause of the previous definition leaves open the possibility that the graph $G - X$ in the first block of quoted text need not be a spanning subgraph of $G$ because if $X$ contains edges incident to leaf vertices, then these vertices won't be in $G-X$.

Am I correct that the authors made a mistake or am I getting lost in the sea of definitions?

1

There are 1 best solutions below

0
On BEST ANSWER

I think you may be conflating the last two statements made in the first quote.

The second statement: "For a subset of , the graph − is the spanning subgraph of with edge set −." holds true.

By the spanning subgraph definition you gave, G-X must be a spanning subgraph. The vertex set, V(G), is unaltered if you remove a subset of edges, and therefore V(G)=V(G-X). Furthermore, E-X is a subset of the edge set E of G. (Thus fulfilling both conditions of a spanning subgraph)

Note: G-X does not need to be an induced subgraph. The final statement of the paragraph you quoted is self-contained. The induced subgraph part of the paragraph only applies to when you're deleting vertices as the book stated.