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.
$\begingroup$
$\endgroup$
1
asked Jun 27, 2012 at 18:27
-
1$\begingroup$ Consider the maximum number of edges an outerplanar graph can have. $\endgroup$– user34709Commented Jun 28, 2012 at 20:45
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
4
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.
-
$\begingroup$ What do you mean by region? How do regions correspond to vertices / leaves? $\endgroup$– genCommented Jun 2, 2018 at 14:51
-
$\begingroup$ @gen Any way in which you legally draw a planar graph in the plane separates the plane into regions. Check out en.m.wikipedia.org/wiki/Dual_graph. $\endgroup$ Commented Jun 2, 2018 at 14:56
-
$\begingroup$ So when you say the regions in the interior form a tree then what you mean is that the corresponding portion of the dual graph forms a tree? $\endgroup$– genCommented Jun 2, 2018 at 15:01
-
1
$\begingroup$
$\endgroup$
4
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.
answered Jul 2, 2012 at 6:27
-
$\begingroup$ Are you linking an IP address? How underground and pre-DNS of you! :-) $\endgroup$– Asaf Karagila ♦Commented Jul 2, 2012 at 6:50
-
$\begingroup$ @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. $\endgroup$ Commented Jul 3, 2012 at 2:08
-
$\begingroup$ @GerryMyerson link is broken, even when adding http:// $\endgroup$– Ory BandCommented Jun 26, 2013 at 17:52
-
$\begingroup$ @Ory, sorry, I can't find the page and don't remember anything useful about it. $\endgroup$ Commented Jun 27, 2013 at 6:30
$\begingroup$
$\endgroup$
1
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.
-
$\begingroup$ 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. $\endgroup$ Commented Jan 10, 2016 at 23:23