3
$\begingroup$

As far as I know, a planar graph is simply defined as a graph that can be drawn in the plane with none of its edges crossing. This I understand.

However, I came across a problem that says: "Every planar graph has a vertex of degree at most five."

enter image description here

In the image above there are nine vertices, one of which has degree 8. None of the edges cross, so why is this not a planar graph?

$\endgroup$
  • 1
    $\begingroup$ The problem you cite says only that there is at least one vertex of degree at most five. That is different than saying all vertices have degree at most $5$. $\endgroup$ – Casteels Apr 15 '15 at 12:17
  • 1
    $\begingroup$ This is planar graph. "Every planar graph has a vertex of degree at most five." in this graph there is also a vertex with a degree less then 5 as you can see. It's easy to prove that if all vertices have a degree higher then 5, so 6 or higher that this graph cannot be planar. You can prove this using Eulers formula for planar graphs. $\endgroup$ – Nescrio Apr 15 '15 at 12:17
3
$\begingroup$

That theorem is meant to be read as follows: "For all planar graphs G, there exists a vertex $v$ of $G$ with degree $5$ or less." You are reading it as "For all planar graphs G and for all vertices $v$ of $G$, $v$ has degree $5$ or less"

$\endgroup$
  • $\begingroup$ Ah, that makes more sense. I'm studying for a graph theory exam at the moment and this little theorem made me doubt the foundations of everything I had studied on the topic -- thanks for clearing it up. I think I need to sleep -- my brain is not operating properly anymore :( $\endgroup$ – Steve Apr 15 '15 at 12:30

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.