# Let $G$ be a planar graph. Suppose that $V = V_4 \cup V_8$. Prove that if $|V_8| = 12$, then $|V_4| \ge 18$

For each $n \in \mathbb N$, define $$V_n = \{v \in V : d(v) = n\}$$

Proof.
Let $G = (V, E)$ be a planar graph.
Suppose that $V = V_4 \cup V_8$.
Suppose that $|V_8|$ = 12.
Since $|V_8| = 12$ and $|V_8| \subseteq V$, $G$ has at least 48 edges by the Handshake Theorem.
...
Therefore, $|V_4| \ge 18$.

So I understand that what I am examining is a graph that has vertices of degree $4$ and vertices of degree 8. $G$ has $12$ vertices of degree $8$, and I want to show that this means I must have $18$ or more vertices of degree $|V_4|$.

I've been given the hint that I want to count the number of vertices and edges of $G$ in terms of $|V_4|$ and $|V_8|$. I'm not entirely sure how to move forward even with this hint. Can anyone give me a pointer in the right direction?

• can u put the question as it is from your text book? – KakaS Apr 19 '16 at 6:15
• The question has all of the information that was given. – Dewick47 Apr 19 '16 at 16:51

## 1 Answer

Say we have $a= |V_4|$. By handshake lemma we have $2E = 8\cdot 12 + 4\cdot a$.

Since $G$ is planar graph we have $E\leq 3V-6$ and thus $a\geq 18$.