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.
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.Sign up to join this community
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.