3
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

Here is another solution, with weaker assumptions. Suppose G tessellates a $k$-gon, where all internal vertices have valence at least 6, and the vertices of the $k$-gon have valence at least 4. Take 2 copies of G and label the vertices of the outermost $k$-cycles as $u_1,\ldots, u_k$ and $v_1,\ldots, v_k$. Then add edges from $u_i$ to $v_i$ and from $u_i$ to $v_{i+1}$, for each $1\leq i\leq k$ and where $v_{k+1}\equiv v_1$. This produces a simple planar graph where every vertex has valence at least 6, which is impossible.

$\endgroup$
4
$\begingroup$

No. If it tesselates a $k$-gon, and the number of internal vertices is $m$, then the number of edges is at least $$e\geqslant (5k+6m)/2=3m+\frac52 k. \quad \quad (A) $$If the number of internal faces is $f-1$, then counting edges by faces we get $$2e\geqslant 3(f-1)+k.\quad \quad (B)$$ But $e=f+(k+m) -2$ by Euler theorem, so $f-1=e-k-m+1$ and by (B) we have $2e\geqslant 3e-3k-3m+3+k$, that is, $$3m+2k-3\geqslant e. \quad \quad (C) $$

(A) contradicts to (C).

$\endgroup$

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.