Which of the following statements is true for every planar graph on n vertices?

Correct statement: The graph has a vertex-cover of size at most 3n/4.

Reason:

• Planar graphs are 4-colorable (Four Color Theorem).

• Color classes are independent sets, so partitioning vertices into four color classes gives at least one class of size at least n/4.

• Therefore the graph has an independent set of size at least n/4, and the complement of any maximum independent set is a vertex cover of size at most n - n/4 = 3n/4.

Why the other statements are false:

• Claim: The graph is Eulerian. Counterexample and explanation: Eulerian requires every vertex to have even degree (and connectivity for an Eulerian circuit). A simple planar graph with an edge between two vertices has vertices of degree 1 (odd), so it is not Eulerian.

• Claim: The graph is connected. Counterexample: Two disjoint triangles form a planar graph that is not connected, so planarity does not imply connectivity.

• Claim: The graph has an independent set of size at least n/3. Counterexample: The complete graph on four vertices (K4) is planar, has n = 4, and its largest independent set has size 1, which is less than 4/3. More generally, taking disjoint copies of K4 yields larger planar graphs with independence number about n/4, so the n/3 bound fails.

Conclusion: The only statement that holds for every planar graph on n vertices is that there exists a vertex cover of size at most 3n/4.