If a graph is planar, them what is the maximum degree any of its vertices can have ? Also, can a planar graph have chromatic number more than 4 based on the Vizing theorem ?Isn't vizing theorem a contradiction to the Four Color Problem ?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
There is no maximum degree for planar graph: the $n$-star (one vertex connected to $n$ others) is always planar, and the central vertex has degree $n$.
This is not in contradiction with the four-color theorem, because Vizing speaks about edge chromatic nunmber, whille the 4-color property is about vertex chromatic number.