1. Prove that v(Г) - e(Г) = 1 for any tree T. (v :vertices and e : edges)
2. Even better, show that v(Г) - e(Г) ≤ 1 for any graph Г, with equality precisely when Г is a tree.
Please see attached file
1. Prove that v(Г) - e(Г) = 1for any tree T. (v :vertices and e : edges)
For the proof we need to introduce a class of special graphs. A tree G is a connected graph without cycles, i.e. any two vertices of G can be connected by a path (a sequences of edges) and there is no path whose starting and ending vertices coincide. To make a tree, we add edges beginning at some existing vertex, already counted, and extend to some new ...
The expert examines undergrad topology vertice proofs. Proofs are analyzed.