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
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. ...
Outerplanar graphs are investigated. The solution is detailed and well presented.