# If graph $G$ is connected and has at least two vertices, prove that there exist vertices $u$ and $v$ so graphs $G-u$ and $G-v$ are connected

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 :)

• 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. – Chickenmancer Jan 23 at 20:42
• 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)? – Haris Jan 23 at 20:50
• 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. – Daniel Jan 23 at 20:50
• Oh.. That looks better indeed. Thanks – Haris Jan 23 at 20:53
• 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). – yamete kudasai Jan 23 at 21:08