by user25783
Last Updated May 16, 2018 14:20 PM

I saw you answered similar questions here, but I wanted to know if I can prove the theorem (= adding an edge to a tree creates a cycle) also like this:

It is known that the definition of aTherefore, when we add one edge to a tree, the tree contains now $n$ edges $((n-1)+1),$ and it is exactly the number of its vertices, so it contains a cycle now.

Is this whole proof correct?

A cycle contains the same number of edges as vertices. But not every graph with this property is a cycle, so your final statement is unjustified.

Some six-vertex graphs with six edges you can find on The House of Graphs that aren't cycles are below (there's plenty of other examples if you'd like more).

You may notice that all of these graphs *contain* a cycle, and in fact that's generally true, but this is precisely the statement you have to prove.

One approach might be to first find a subgraph which has minimum degree $2$, and then find a cycle inside this subgraph in the usual way.

Also, a final nitpick: usually, only the first two properties you gave (connected and has no cycles) are the *definition* of being a tree. The third property, of course, is likely to be something you prove about trees fairly early on, starting from that definition.

- Serverfault Help
- Superuser Help
- Ubuntu Help
- Webapps Help
- Webmasters Help
- Programmers Help
- Dba Help
- Drupal Help
- Wordpress Help
- Magento Help
- Joomla Help
- Android Help
- Apple Help
- Game Help
- Gaming Help
- Blender Help
- Ux Help
- Cooking Help
- Photo Help
- Stats Help
- Math Help
- Diy Help
- Gis Help
- Tex Help
- Meta Help
- Electronics Help
- Stackoverflow Help
- Bitcoin Help
- Ethereum Help