# Planar Graphs and Skew Binary Subspaces

Let $G$ be a planar triangulation on $3m$ edges and $m+2$ vertices. Let $A$ be the binary matrix obtained from the incidence matrix of $G$ by deleting a row (equivalently the rows of $A$ form a basis of the cocycle space of $G$ over $GF(2)$).

My question is: What additional criteria must be assumed (if any) to guarantee there is an $(m-1)$-dimensional subspace of $GF(2)^{m+1}$ which does not contain any column of $A$?

Any relevant references would be much appreciated.

The question has been resolved by Chris Godsil on Maths Overflow. I repost it here for completeness:

What follows is all quite standard, iirc it's in Aigner's book "Combinatorics" but my copy's out on loan....

Let $B$ be the vertex-edge incidence matrix of the graph. (Nothing's gained by deleting a row.) We want a subspace of codimension two in $GF(2)^{m+2}$ containing no column of B. If a and b are distinct non-zero vectors indexed by the vertices of $G$ and $x$ is a column of $B$, we have a map $\rho _{a,b}$ that sends $x$ to $(a^Tx,b^Tx)$ and $a^⊥∩b^⊥$ is a subspace of codimension two that does not contain a column if and only if $0$ is not in the image of $ρ_{a,b}$.

If we identify $V(G)$ with the standard basis for $GF(2)^{m+2}$ then the map that assigns the vector $ρ_{a,b}(ei)$ to the vertex $i$ is a proper 4-colouring of the vertices of $G$, as you can easily check. Hence a necessary condition is that $G$ be 4-colourable.

On the other hand, if $G$ is 4-colourable then we can colour it with the four elements of $GF(2)^2$. Let $a$ be the vector such that $a_i$ is the first coordinate of the colouring of the vertex $i$ and let $b$ be the vector such that $b_i$ is the second coordinate. The $ρ_{a,b}(e_i+e_j)≠0$ if $ij∈E(G)$ and so the kernel of $ρ_{a,b}$ is a subspace of codimension two that does not contain a column of $B$. (If $a=b$ we have a 2-colouring, which is impossible.)

So your question is equivalent to the 4-color theorem.

• It is considered good practice not to post in parallel on both sites, and at least wait a few days, so the discussion threads don't overlap. just FYI Jul 14, 2011 at 16:04