I would like to know if proof below is correct for this problem.

Let $n$ be the number of vertices of the graph $G$.

As $G$ is connected graph, that means there are at least $n-1$ edges in the graph.

  • If $G$ has exactly $n-1$ edges and $n$ vertices, it is a tree. Tree has at least two leaves. Let $u$ and $v$ be those leaves. By removing a vertex of degree 1 from a connected graph, it stays connected. That means $G-u$ and $G-v$ are connected too.
  • If $G$ has more than $n-1$ edges, and it is connected, we can construct a spanning tree for all the vertices of the graph $G$. That spanning tree also has at least two leaves. Let $u$ and $v$ be those leaves. These vertices are either leaves in $G$ or are connected with some another vertex in $G$ so they make a cycle. Either way, $G-u$ is connected, so is $G-v$.

Thanks :)

  • $\begingroup$ If $V(G)$ is finite, then you can use induction on the number of vertices. Since the set is finite, there is also a "longest path" which you can use to base your argument. The base case should begin with $|V(G)|=2,$ and $G$ is connected, then pick $u$ and $v$ as the only two vertices. Then proceed by an argument about the longest path. $\endgroup$ – Chickenmancer Jan 23 at 20:42
  • $\begingroup$ Yeah. That seems logical, but it was not obvious to me while I was trying to prove this statement. Thank You! Could you also please say if this proof may be considered correct or not (the proof I posted above)? $\endgroup$ – Haris Jan 23 at 20:50
  • $\begingroup$ I would just try to explain the final point better.... Notice that it does not matter whether $u$ and $v$ are leaves or not in the original graph. The important part is to say that since $u$ is a leaf in the chosen spanning tree, removing $u$ will not disconect the tree and then this new tree that was formed is a spanning tree of $G-u$, implying it is connected. $\endgroup$ – Daniel Jan 23 at 20:50
  • $\begingroup$ Oh.. That looks better indeed. Thanks $\endgroup$ – Haris Jan 23 at 20:53
  • $\begingroup$ Your proof is correct! And you don't have to divide in cases, just take a spanning tree from the beginning (this tree will be everything in the first case). $\endgroup$ – yamete kudasai Jan 23 at 21:08

Your Answer

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

Browse other questions tagged or ask your own question.