Does anyone know an elegant proof to the fact that every outerplanar graph has a vertex of degree at most 2 (and hence is 2-degenerate, since every subgraph is also outerplanar).
I have a proof by induction (on the number of vertices) in mind, but it is long and somewhat cumbersome (it splits into a few cases). Can anyone point me to a more elegant proof?
Maybe one can do it using the dual graph - if the dual graph is circle-free then we are done, but I couldn't find an easy argument for that either.
Thanks in advance for any help.
3 Answers
$\begingroup$Observe that every outerplanar graph can be made into a maximal outerplanar graph of the same order. The regions in the interior of a maximal outer planar graph form a tree since if there was a cycle, that would surround a vertex, contradicting outerplanarity. Trees have at least two leaves. Any region corresponding to a leaf will have a vertex of degree 2. This vertex must have had degree less than or equal to 2 in the original graph.
$\endgroup$ 4 $\begingroup$There is a proof at 203.208.166.84/masudhasan/6.1.20.proof.pdf, but it's probably no simpler than what you already have.
$\endgroup$ 4 $\begingroup$Sketch of proof: by contradiction. Assume that an outerplanar graph $G$ exists whose every vertex has degree $\ge3$. $G$ is not a tree, since a tree trivially has a vertex with degree $\le2$. Therefore it encloses at least one interior region, and has no "naked branches," either, (such as would terminate with degree 1.) Consider the cycle traversing the unbounded face of the graph. If it is not Hamiltonian, then it has at least one subcycle with no vertices repeated, connected to the rest of the graph at only one of its vertices, i.e. "pinched off" from the rest of the graph. This subgraph is Hamiltonian and outerplanar, but we can show that every Hamiltonian outerplanar graph has at least two vertices of degree exactly two, and at least one of these has total degree 2 in $G$, a contradiction.
$\endgroup$ 1
