Let $(V,E)$ be a graph where between each two vertices $v_1,v_2\in V$ there exists only one path. Then

  • The graph has no cycles.
  • Adding a new edge creates a cycle.

I have no idea how it could be proven.

  • $\begingroup$ which kind of special kind of graph has no cycles and and has a single path connecting any two vertices? try to draw this structure and see why adding any edge would cause a cycle. then try to formalize this. $\endgroup$ – LearnToMath Oct 29 '14 at 11:06

First part by contradiction: If there would be a cycle, then this cycle would have at least 3 vertices $v_1$, $v_2$, and $v_3$. Since it is a cycle, there is one path from $v_1$ to $v_2$ through $v_3$ and another that does not go through $v_3$. This is contradiction to the assumptions.

Second part: connecting a new edge, say $(v_1,v_2)$ creates a path between $v_1$ and $v_2$. Since both vertices were already connected by another path, a cycle is closed.

| cite | improve this answer | |

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.