Take the 2-minute tour ×
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.

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|improve this question
1  
Consider the maximum number of edges an outerplanar graph can have. –  user34709 Jun 28 '12 at 20:45

2 Answers 2

up vote 2 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|improve this answer

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.

share|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

Your Answer

 
discard

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.