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?
Best Answer
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.