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

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?

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

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$.


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.