Explore BrainMass

Explore BrainMass

    Undergrad Topology Vertice Proofs

    This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

    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.

    © BrainMass Inc. brainmass.com February 24, 2021, 2:36 pm ad1c9bdddf


    Solution Preview

    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 ...

    Solution Summary

    The expert examines undergrad topology vertice proofs. Proofs are analyzed.