0
$\begingroup$

Possible Duplicate:
planar graphs and vertices of degree $5$

final season is upon us, and i'm getting stuck on these practice problems.

Let $G$ non-null, simple, planar with no vertex of degree less than $4$.

Is it true that $G$ must have two vertices of degree $5$ which are joined by a path of length less than $10^6$ ? Pproperties I think could be used:

  • $\sum \deg(v)=2|E(G)|$

  • For $G$ simple and planar, let $n_i$ be the number of vertices of $G$ of degree $i$. Then \begin{align} 6\cdot n_0 + 5\cdot n_1 + 4\cdot n_2 + 3\cdot n_3 + 2\cdot n_4 + n_5 - n_7 - 2\cdot n_8 - \cdots - (i-6) \cdots n_i ≥ 12 \end{align}

  • 0
    thanks! though they seem to be answering question b) which I've figured out.2012-12-02

0 Answers 0