I had a question on my exam and answered it using what I believe to be an Exhaustive Proof. The teacher marked it wrong, and while I understand there is a simple answer to the question, I would like to understand why my answer is wrong. The question is as follows:
Prove or disprove – A planar graph with 8 vertices and 13 edges can be 2 vertex colorable.
My answer:
A graph has a vertex coloring of 2 if and only if it is bipartite, and since the graph in question is planar, than it can not contain the subgraph k3,3 and the complete subgraph k5. This leaves the only possible bipartite graph with 8 vertices as k1,7 and k2,6, which both don't have 13 edges (used a table to show this). C8, which is bipartite does have 8 vertices but only 8 edges, and a tree with 8 vertices cannot have 13 edges. This proves that no matter what configuration of a planar graph with 8 vertices and 13 edges, it can not be 2 vertex colorable.
Would appreciate your thoughts, comments and criticism.
Thanks.
Best Answer
Your cases are not exhaustive. You can still have a subgraph of $K_{4,4}$ that is planar and is not a subgraph of $K_{1,7}$, $K_{2,6}$, or $C_8$. Think, for example, of the graph of a cube. Also, you seem to be confusing edges and vertices. The question asks for a graph with $8$ vertices and $13$ edges, but you seem to be talking about graphs with $8$ edges.
While the statement is correct; a planar graph cannot have $8$ vertices and $13$ edges, a better approach is to use Euler's formula. Let $G$ be a planar graph with $8$ vertices and $13$ edges. Without loss of generality, $G$ is connected, so $v + f - e = 2$ (assuming $G$ is connected). This gives us $f = 7$. Now if $G$ is $2$-colorable, then every face has at least $4$ edges on it. So we can "recount" the vertices: we have $7$ faces, each with at least $4$ edges on them, and each edge appears in at most two face. So $e \ge 7 \cdot 4 / 2 = 14$, a contradiction.