# Trees and Graphs : Outerplanar Graphs

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.

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.