1
$\begingroup$

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

| cite | improve this question | | | | |
$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Clement C. May 2 '18 at 17:55
  • $\begingroup$ F is G+one edge. If F is not connected, then it MUST contain a cycle. @ArsenBerk. $\endgroup$ – Clement C. May 2 '18 at 18:00
  • $\begingroup$ 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. $\endgroup$ – Joffan May 3 '18 at 14:18
2
$\begingroup$

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

| cite | improve this answer | | | | |
$\endgroup$

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.