# Proving every planar graph have vertex cover of size of at most 3n/4

Question title says it all: How it can be proved that every planar graph on n vertices have vertex cover of size of at most 3n/4.

I came across this fact when I was reading a textbook. However I am unsure if this is in fact correct. And if it is how it can be proved?

• What is $n$? Number of vertices? Of edges? – hardmath Dec 11 '14 at 20:18

It's a consequence of the four color theorem. Take a planar graph $G$, and color it in 4 colors. All vertices except the ones in the color class of greatest size form a vertex cover consisting of at most $3|V(G)|/4$ vertices.
• @awellwisher The color class of greatest size must have at least $n/4$ vertices (if it had fewer, there would be fewer than $n$ vertices total). So there must be at most $n - n/4 = 3n/4$ other vertices. – Perry Elliott-Iverson Dec 12 '14 at 15:39
• @Mahesha999 Yes, there is an independent set in any planar graph of size at least $n/4$. – Perry Elliott-Iverson Dec 17 '15 at 20:58
• I was revising these concept again. Now, it is not making sense to me how minimum independent set size will be $n/4$. It should be always 1, right? Since its "set of vertices in a graph, no two of which are adjacent". Also it is not making me sense that size of vertex cover is at most $3n/4$, as it should be $n$ since its "set of all vertices is a vertex cover". – anir123 Jan 30 '17 at 18:52