# How to prove that graph has cycle?

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.

• 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. Oct 29, 2014 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.