Discrete mathematics- Graph without any cycles

230 Views Asked by At

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

1

There are 1 best solutions below

0
On

There are two possibilities.

  • 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$.