I am reading a discrete mathematics textbook. In the section of trees, it listes out the following five properties of a tree.
$(i)$ T is a tree if and only if any two of its vertices are connected by exactly one path.
$(ii)$ T is a tree if and only if it is connected and the removal of any one edge results in the graph becoming disconnected.
$(iii)$ If T has order $n$, then it is a tree if and only if it contains no cycles and has $n-1$ edges.
$(iv)$ If T has order $n$, then it is a tree if and only if it is connected and has $n-1$ edges.
$(v)$ T is a tree if it contains no cycles, but the addition of any new edge creates exactly one cycle.
I understand the first four part and their proofs from the textbook. I feel the fifth one is weired. The proof given by the textbook is as follows:
Proof: If T is a tree, then by definition it is connected and contains no cycles. Now if we add an edge between two existing vertices A and B, then there are now exactly two paths from A to B. Hence there is now a single circle which starts and finishes at A, and travel either direction via B. The cycle through B is the same cycle since it contains the same set of edges. Hence, exactly one cycle is created.
First, the proof is logically wrong since we are required to prove that
T contains no cycle, but the addition of any new edge creates exactly one cycle. $\Rightarrow$ T is a tree. Not $\Leftarrow$.
Secondly, we can prove $\Rightarrow$. Let's T contains no cycle. It is either disconnected or connected. If it is connected then, by definition, it is a tree. If it is disconnected, we could always find vertices A and B such that we add one edge between them, it doesnot produce a cycle. Then if we can prove it $(\Rightarrow)$, then isn't it an if and only if condition? I mean
T contains no cycle, but the addition of any new edge creates exactly one cycle. $\Leftrightarrow$ T is a tree.
Best Answer
You are right, but I am fairly certain that the book meant for v) to be an if and only if as well, just like the other four .... I mean, it seems like they propose these five as five different ways to define a tree. It seems weird that they really meant that fifth one as only going one way ... when in fact it goes both ways (as you show), and when the only way they show is indeed the other way than stated. So I think it was just an oversight that they didn't state 'if and only if'.
As such, I would say the proof they gave wasn't so much wrong, but that it is incomplete ... They indeed only proved one direction. So you did the right thing to demand the other direction!
Also, your proof of going the other way is correct, though I think it would be a little sharper by switching your two parts. That is, I would say:
Assume T is a graph without cycles, but adding any edge will produce a cycle. Now, if T is disconnected then we can add an edge without getting a cycle, which we assumed could not happen, and so this tells us that T is not disconnected, i.e. T must be connected. So T is a connected graph without cycles, i.e. a tree.