Explore BrainMass

# Trees and Graphs : Outerplanar Graphs

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

What bound is given for X(G) by the theorem "for every graph G,
X(G)<=1+max &(G') ,where the maximum is taken over all induced subgraphs G' of G" in the case that G is
a) a tree?
b) an outerplanar graph.

Note: -&(G') this sign represent the minimum degree of G'. Yes it is that minimum
-A graph G is outerplanar if it can be embedded in the plane so that every vertex of G lies on the boundary of the exterior region. A graph G is outerplanar if and only if G=K1 is planar.A graph G is outerplanar if and only if it contains no subgraphs that is a subdivision of either k4 or k2,3.
A graph G is outerplanar of order n>=2 and size m, then m<=2n-3.
Page 145 of the book Graph and Digraph" 4ed be G Chartrand and...
What does outerplanar graph?
draw a graph please.

© BrainMass Inc. brainmass.com March 4, 2021, 7:29 pm ad1c9bdddf
https://brainmass.com/math/graphs-and-functions/trees-graphs-outerplanar-graphs-104039

#### Solution Preview

Please see the attached file for the complete solution.
Thanks for using BrainMass.

What bound is given for X(G) by the theorem"for every graph G,
X(G)<=1+max &(G') ,where the maximum is taken over all induced subgraphs G' of G" in the case that G is
a) a tree?

Since any induced subgraph G' of a tree is a tree or a forest, we know that the minimum degree of G' is therefore 1. Hence,

So, the upper bound is 2, implying we can colour any tree by two colours.

b) ...

#### Solution Summary

Trees and outerplanar graphs are investigated. Sign representations for minimum degrees are determined.

\$2.49