Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
Consider the maximum number of edges an outerplanar graph can have. – user34709 Jun 28 '12 at 20:45
up vote 1 down vote accepted

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.

share|cite|improve this answer
What you have done can be done easier by just observing that every outerplanar graph can be extended to a maximal outerplanar graph, which is guaranteed to be Hamiltonian. Also, just because you have a sub graph with degree 2 doesn't mean your original graph has a vertex of degree 2. For example The corona ofK_3 is outerplanar but does not have the properties indicated. The hardest part of such a proof is what you have neglected, which is to show that a hamiltonian(or maximal) outerplanar graph has a vertex of degree at most 2. – Sean English Jan 10 at 23:23

There is a proof at, but it's probably no simpler than what you already have.

share|cite|improve this answer
Are you linking an IP address? How underground and pre-DNS of you! :-) – Asaf Karagila Jul 2 '12 at 6:50
@Asaf, I tried to link that address, but the software wouldn't let me. It said I should put it in a "code block", but I don't know what that is, so I just deleted the "http" part. Anyway, what's in my answer is what was in my browser, I don't know what other link to give. – Gerry Myerson Jul 3 '12 at 2:08
@GerryMyerson link is broken, even when adding http:// – Ory Band Jun 26 '13 at 17:52
@Ory, sorry, I can't find the page and don't remember anything useful about it. – Gerry Myerson Jun 27 '13 at 6:30

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.