I am thinking about something along these lines:

Assume that $G$ is connected and let $u$ and $v$ be two vertices that are disjoint. In order for $u$ and $v$ to be connected there exists another vertex $w$ such that $uw$ and $wv$ are connected. Now since $u$ and $v$ are both connected with $w$ then $G$ is a tree.

Does that work OR is it more complicated than that?

  • $\begingroup$ Did you mean "Assume $G$ is connected?" $\endgroup$ – angryavian Apr 11 at 0:32
  • $\begingroup$ @angryavian Yes correct! sorry about that $\endgroup$ – Hidaw Apr 11 at 0:35

You would need more than just there be a connected graph on $uw$ and a connected graph on $wv.$ Here is a way I would go about it.

Since every vertex of $G$ is linked by a path, $G$ is connected. If $G$ had a cycle, and $u,w$ were on that cycle, then they would be connected by two distinct paths. This cannot happen, so $G$ has no cycles. The only connected acyclic graphs are trees, hence $G$ is a tree.


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.