0
$\begingroup$

Suppose that $v$ is a vertex of degree $1$ in a connected graph $G$ and that $e$ is the edge incident on $v$. Let $G′$ be the sub- graph of G obtained by removing $v$ and $e$ from $G$. Must $G′$ be connected? Why?

My solution:
If I understand correctly I think G′ will be disconnected. The reason is that for graph to be connected each pair of vertexes must be connected. By removing one vertex and edge the node will be disconnected.

Is this correct?

$\endgroup$
  • $\begingroup$ Are you familiar with what it means for $v$ to be degree 1? $\endgroup$ – dalastboss Jan 4 '15 at 4:11
2
$\begingroup$

If the vertex $v$ has degree $1$, then $v$ is incident to only one edge, namely $e$. This means that $v$ is connected to the rest of $G$ by way of only one edge, and $v$ will only have one other vertex connected to it. So removing $v$ and its only incident edge $e$ from connected graph $G$ means what?

$\endgroup$
  • $\begingroup$ If I understand correctly I think G′ will be disconnected. The reason is that for graph to be connected each pair of vertexes must be connected. By removing one vertex and edge the node will be disconnected. $\endgroup$ – Nadia S Jan 4 '15 at 21:24
  • $\begingroup$ But you arent just disconecting it, you are removing it completely! Think about it a bit more. Maybe draw some graphs as examples and see what happens. $\endgroup$ – cirpis Jan 4 '15 at 21:35
  • $\begingroup$ @NadiaS, the thing is that you are removing $e$ (which is a "cut-vertex" or "bridge" by the way). Removing $e$ by itself would disconnect the graph, leaving the rest of $G$ and the last vertex $v$ all by itself. But, in your question, we are also removing $v$. So we disconnect the graph by removing $e$, but then we also remove vertex $v$, which is the only disconnected vertex. Try this: draw a bunch of connected graphs with a vertex $v$ that has degree $1$. Label $v$ and the edge $e$ incident to $v$. Then erase both $v$ and $e$. You will find $G'$ is always connected. $\endgroup$ – Sultan of Swing Jan 4 '15 at 23:36
1
$\begingroup$

Think about the problem a little. What does a vertex of degree $1$ look like? What does a cut-edge look like?

$\endgroup$

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.