1
$\begingroup$

An outerplanar graph is a connected plane graph that can be drawn in such a way that all it's vertices are on the outer face.
I want to show that for every $G$ outerplaner graph with $n$ vertices and $m$ edges, $m\leq 2n-3$
I tried induction and I have a graph on $n$ vertices. I want to take one that has exactly 2 edges to it, so when I remove it will fit.
Just to be clear, I started my proof by saying that if G is a tree then $m=n-1$ and it's all good.
How can I show that exists a vertice with 2 edges?

$\endgroup$
1
  • $\begingroup$ Can I say that since there is a circle in $G$, one of it's vertices has to be with 2 edges? otherwise the "middle" edge of all of the has to intersect each other in the center of the circle or to meet with a defferent vertice in the middle (contradicting it's outerplaner)? $\endgroup$ Jun 29 '15 at 16:53
2
$\begingroup$

If the graph is $K_1$ it is false since $m=0$ and $n=1$.

Let $n\geq 2$: If the graph is a tree it has $n-1\leq 2n-3$ edges.

We suppose the graph is not a tree:

If you add the number of edges each face has you get $2m$. This sum is at least $3(f-1)+n$ since the inner faces have at least $3$ edges and the outer face has at least $n$ edges (since the outer edges form a connected graph that is not acyclic). So $2m\geq3f+n-3\implies 3f \leq 2m+3-n\implies f\leq\frac{2m+3-n}{3}$.

Now we use Euler's formula:

$2=n+f-m\leq n+\frac{2m+3-n}{3}-m\implies 6\leq 3n+2m+3-n-3m\implies m\leq2n-3$

$\endgroup$
10
  • $\begingroup$ That is another way to do it. Thanks. But how can I show that there is a vertice with 2 edges in $G$? If you can reffer to my comment above. $\endgroup$ Jun 29 '15 at 16:58
  • $\begingroup$ A vertex with degree exactly $2$ in $G$? $\endgroup$
    – Asinomas
    Jun 29 '15 at 16:59
  • $\begingroup$ A vertex with degree exactly 2 in G... $\endgroup$ Jun 29 '15 at 16:59
  • $\begingroup$ that is not necessarily true look at this picture upload.wikimedia.org/wikipedia/commons/thumb/7/7d/… $\endgroup$
    – Asinomas
    Jun 29 '15 at 17:01
  • $\begingroup$ For trees $m=n-1$ as I said, and the case above is only for $G$ which are not trees. $\endgroup$ Jun 29 '15 at 17:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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