Size of an independent set of planar graph with $n$ vertices

Question

You have a simple graph with $n$ vertices.

Prove that there exist an independent set which size is at least $n/6$.

I have no idea how to start it. I know that, for planar graphs, $e\leq 3v-6$, where $v$ is the number of vertices and $e$ is the number of edges of the graph. Should I use this somehow?

edit: I found this question:

Prove $\forall$ graphs, $\alpha(G) \ge \frac{n}{\Delta(G)+1}$

So now I only have to show that the statement is true for graphs, where $\Delta (G)\ > 5$.

Answer 1

This is a consequence of the Six Color Theorem, which states that every planar graph has a proper coloring that makes use of six colors or less. In fact, a set of vertices colored with the same color must be independent, and since there are only six colors, the pigeonhole principle ensures that there should be $n/6$ vertices with the same color.

To prove the Six Color Theorem you must consider the fact that in every planar graph there is a vertex with degree less or equal to $5$.

This fact follows from the formula you wrote: $E\le 3V-6$. Notice that this implies that, considering $G$ a planar graph, $$\sum_{v\in V(G)}deg(v) = 2E\le6V-12 \therefore \sum_{v\in V(G)}\frac{deg(v)}{V}\le6-\frac{12}{V}<6$$ That is, the average degree is less than 6.

If there is a planar graph that needs seven or more colors to be colored, then there is such a graph, say $G$, with a minimum number of vertices. Since $G$ is planar, there is $v$ vertex of $G$ with a degree less than or equal to $5$. Since $G$ has a minimum number of vertices, $G-v$ can be colored with $6$ or less colors. Let $c:V(G-v)\rightarrow\{1, 2, 3, 4, 5, 6\}$ be such a coloring. Now consider the coloring $c':V(G)\rightarrow\{1, 2, 3, 4, 5, 6\}$ such that:

• $c'(u)=c(u)$ if $u\in V(G-v)$.
• $c'(v)\in \{1, 2, 3, 4, 5, 6\}-\{c(u): u\in N(v)\}$, where $N(v)$ denotes the neighboring vertices of $v$.

Since $|N(v)|\le 5$, $\{1, 2, 3, 4, 5, 6\}-N(v)\neq\emptyset$, therefore, $c'$ is well defined and represents a proper coloring. Contradiction. So the theorem holds.