patternMinor
Is there a low degree vertex in planar graphs?
Viewed 0 times
degreevertexlowgraphsplanarthere
Problem
A book I read states "Since $G$ is planar, $G$ has a vertex $v$ of degree at most 5".
- Is this true?
- Why?
- Does this theorem have a name?
Solution
- Yes, this is true.
- It is a direct consequence of Euler's formula. The formula entails that the average degree is strictly less than 6, which implies the existence of a vertex of degree at most 5.
- It doesn't have a name in itself, but Euler's formula is the overall subject.
Context
StackExchange Computer Science Q#16800, answer score: 6
Revisions (0)
No revisions yet.