Skip to main content
Became Hot Network Question
removed capitals from title
Link
YCor
  • 63.9k
  • 5
  • 187
  • 285

Planar Graphgraph of High Valencehigh valence

Source Link
Daps
  • 540
  • 2
  • 8

Planar Graph of High Valence

A classic result in graph theory tells us that any planar graph must have at least one vertex with valence no bigger than 5. On the other hand, there exist examples of planar graphs that are 5-regular (e.g. the skeleton of the icosahedron). My question is, is there a planar graph $G$ satisfying

  1. there are no multiple edges in $G$;
  2. $G$ tessellates a polygon;
  3. all internal vertices (the ones contained in the interior of the polygon) have even valence $\geq 6$.
  4. all vertices have valence $\geq 5$ (including the vertices of the polygon).

Note that if such $G$ exists, some vertices of the polygon must be 5-valent. Thank you in advance for any helpful insight.