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?

  • $\begingroup$ What is $n$? Number of vertices? Of edges? $\endgroup$ – 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.

  • $\begingroup$ Thanks @perry but can I get a bit more elaboration about how 3n/4 number comes? any link? $\endgroup$ – anir123 Dec 12 '14 at 9:10
  • $\begingroup$ @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. $\endgroup$ – Perry Elliott-Iverson Dec 12 '14 at 15:39
  • $\begingroup$ Does that translates to: Independent set in planar graphs have size at least n/4 ? $\endgroup$ – anir123 Dec 17 '15 at 20:34
  • 1
    $\begingroup$ @Mahesha999 Yes, there is an independent set in any planar graph of size at least $n/4$. $\endgroup$ – Perry Elliott-Iverson Dec 17 '15 at 20:58
  • $\begingroup$ 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". $\endgroup$ – anir123 Jan 30 '17 at 18:52

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.