1
$\begingroup$

I want to know if adding an edge to a undirected acyclic graph introduces no new vertex to the undirected acyclic graph then therefore we can say that adding this edge creates a cycle? I am confident this is correct, but I am looking for a formal proof on this if it is true(preferably a published paper that shows this).

My take is that when you add 1 edge to a undirected we can...

  • Introduce 1 new vertex to the undirected acyclic graph => we still have a undirected
    acyclic graph

  • Introduce 2 new vertices to the undirected acyclic graph => we have two connected components that are undirected and acyclic.

  • Introduce 0 new vertex to the undirected acyclic graph => we create a cycle, clearly this adds at least another path to reach the vertices of this edge.

$\endgroup$
  • 1
    $\begingroup$ If we start with an undirected graph with several components (so a forest, not a tree) then we can add an edge between the (existing) nodes of two different components without creating a cycle. $\endgroup$ – Hendrik Jan Nov 25 '16 at 0:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.