Maximum DEgree of a planar graph

825 Views Asked by At

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 ?

1

There are 1 best solutions below

0
On BEST ANSWER

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 number, while the 4-color property is about vertex chromatic number.