2

I am having trouble proving this question. I am also having trouble visualizing how this works, using a binary tree as an example. I don't see how adding an edge creates one cycle? Isn't a cycle supposedly a closed chain path ?

greatShark
  • 21
  • What definition of tree are you using? There are many equivalent statements for what a tree is, one of which is the one you give above. – JMoravitz Feb 19 '16 at 23:06
  • Try reading the following: http://math.stackexchange.com/questions/325279/proving-a-simple-connected-graph-is-a-tree-if-adding-an-edge-between-two-existin?rq=1, http://math.stackexchange.com/questions/1118176/proving-if-g-has-no-cycles-but-by-adding-one-edge-between-any-two-vertices-wil?rq=1, http://math.stackexchange.com/questions/1569073/how-can-i-prove-that-by-adding-one-edge-to-g-you-create-a-cycle-in-g?rq=1 – JMoravitz Feb 19 '16 at 23:10
  • Suppose that $u$ and $v$ are distinct vertices of a tree $T$ that are not already joined by an edge, and you add the edge $uv$. If $u$ is an ancestor of $v$, the path from $u$ through $T$ to $v$ and then back to $u$ by the new edge is a cycle. Similarly if $v$ is an ancestor of $u$. Otherwise, let $w$ be the latest common ancestor of $u$ and $v$; then the path through $T$ from $u$ to $w$, followed by the path through $T$ from $w$ to $v$, followed by the new edge is a cycle. – Brian M. Scott Feb 19 '16 at 23:14
  • If assuming "the same vertex set" as one comment in Igor Rivin's answer says, this QA is helpful. – An5Drama Feb 05 '24 at 09:24

1 Answers1

1

This is false as stated, since you can certainly extend a leaf node to get another tree. However, if you keep the vertex set the same, that is true, because if there are two cycles, you can remove an edge from one, and an edge from the other to get a tree which has one edge fewer than the tree you started with. But all trees on $n$ vertices have $n-1$ edges.

Igor Rivin
  • 25,994
  • 1
  • 19
  • 40
  • 1
    I think the question assumes the same vertex set – Shailesh Feb 19 '16 at 23:08
  • The statement "add an edge" is in my opinion at least distinct from the statement "add an edge and a vertex." It is safe to assume that a new vertex will not be added as well and the edge must be between existing vertices. In either case, this doesn't answer the OP's question as to why this might be true or give any intuition as to how to visualize the scenario. – JMoravitz Feb 19 '16 at 23:08
  • @JMoravitz Different people mean different things by "add an edge". – Igor Rivin Feb 19 '16 at 23:11