Explore BrainMass

Explore BrainMass

    Outerplanar Graphs

    Not what you're looking for? Search our solutions OR ask your own Custom question.

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

    A graph is outerplanar if it can be embedded in the plane so that every vertex lies on the boundary of the exterior region. Prove the following:

    If G = G(p, q) is outerplanar with p >= 2, then q <= 2p - 3.

    © BrainMass Inc. brainmass.com March 4, 2021, 8:11 pm ad1c9bdddf

    Solution Preview

    Proof. Note that the fact that G is outplanar if and only if H=G+K_1 is planar. You can prove it very easily.

    Now consider the graph H=G+K_1. ...

    Solution Summary

    Outerplanar graphs are investigated. The solution is detailed and well presented.