3
$\begingroup$

This is a question on Graph Theory. The book says :

1) If $v$ is a vertex in $G$, then $G-v$ is the subgraph of $G$ obtained by deleting $v$ from $G$and deleting all edges in $G$ which contain $v$.

If a node is deleted, it can either give birth to $1$ or more subgraphs.

2) If $e$ is an edge in $G$, then $G-e$ is the subgraph of $G$ obtained by simply deleting the edge $e$ from $G$.

Does the 2nd point mean that if an edge $e$ is deleted from a graph $G$, we can obtain a minimum of $2$ sub-graphs? With one sub-graph($G_1$) consisting of one node of the deleted edge $e$ and the other sub-graph($G_2$) consisting of the other and the only node(trivial graph)?
Is my understanding correct? Because the book nowhere mentions this.

$\endgroup$
2
$\begingroup$

The subgraph being referred to in (2) is the set of all edges and vertices from the original graph, except the deleted edge $e$.

The subgraph wasn't "born" in the sense that it was a subgraph of the original graph all along.

There are also usually other "common" subgraphs, i.e. $G'$ which is a subgraph of $G$ and a subgraph of $G - e$. What this is saying, essentially, is that there is at least one such $G'$. The case where there is only one is if $G$ is just one vertex and one edge (a loop); the only subgraphs of $G$ are $G$ itself and the lone vertex (no edges). The only subgraph of $G - e$ is the lone vertex.

$\endgroup$
  • $\begingroup$ Does the empty graph count as a subgraph? In the same way as $\emptyset\subset A$ for every $A$, or is there some added stipulation that a graph is required to have $|V(G)|\geq 1$? $\endgroup$ – JMoravitz Dec 11 '14 at 19:17
  • 2
    $\begingroup$ @JMoravitz The empty graph (having no vertices or edges) is technically a subgraph of every graph, but in almost all cases the empty graph is assumed to be excluded from statements of the form "all graphs" or "all subgraphs of" because it forms a trivial counterexample to most sensible claims. However, a lot of people who've thought about the idea seem to think there's no reason to even allow a graph with no vertices in the first place. See Harary and Read, "Is the Null Graph a Pointless Concept?" (1973) $\endgroup$ – Nick Dec 11 '14 at 19:20
  • 1
    $\begingroup$ @BaronVT, yes thank you! I forgot to consider a self loop, in which case, one subgraph $G'$ can be obtained. $\endgroup$ – Siddharth Thevaril Dec 11 '14 at 19:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.