# Discrete mathematics- Graph without any cycles

Could someone please explain this and the logic behind it?

Graph $G$ is a graph without any cycles (the definition of a cycle- closed path with at least $3$ edges and no repetitions of vertices) and with $2$ connected components. We get graph $F$, if we add one edge to graph $G$. Prove, that graph $F$ contains a cycle if and only if it is not connected.

Best regards

• If $F$ is connected, it means the edge you added was between the two connected components of $G$ (which was not connected), so it doesn't create any cycle. If $F$ is not connected, then this means you added the edge inside one of the two connected components of $G$: this CC was connected without cycle (thus a tree), you add an edge -- this creates a cycle. – Clement C. May 2 '18 at 17:55
• F is G+one edge. If F is not connected, then it MUST contain a cycle. @ArsenBerk. – Clement C. May 2 '18 at 18:00
• Your specification of what a cycle is, makes it appear that a closed path of $2$ edges or even $1$ edge is possible but excluded from the definition -i.e. that $G$ and $F$ are not necessarily simple graphs. And if we do not have the guarantee that $G$ and $F$ are simple graphs, the statement is not true. – Joffan May 3 '18 at 14:18

• If the edge you add joins two vertices $v,w$ which were in the same connected component of $G$, then you will create a cycle. There was already a path from $v$ to $w$, and adding the edge $(v,w)$ closes the path into a loop.
• If the edge you add joins two vertices $v,w$ which were in different connected component of $G$, then the new graph will be connected. To walk from some vertex $s$ and $t$ which were originally in different components, follow the path from $s$ to $v$, then the new edge $(v,w)$, then the path from $w$ to $t$.