<p>The question has been resolved by Chris Godsil on <a href="https://mathoverflow.net/questions/70225/planar-graphs-and-skew-binary-spaces">Maths Overflow</a>. I repost it here for completeness:</p>

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

<p>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}$.</p>

<p>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.</p>

<p>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.)</p>

<p>So your question is equivalent to the 4-color theorem.</p>

CC BY-SA 3.0
2011-07-14T16:04:38.717Z
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
Suresh Venkat
CC BY-SA 3.0
2011-07-14T10:30:56.110Z
2011-07-14T10:30:56.110Z
2017-04-13T12:57:54.777Z
Einoma Kalaintzis
<p>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)$).</p>

<p>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$?</p>

<p>Any relevant references would be much appreciated. </p>

CC BY-SA 3.0
2011-07-13T19:03:26.523Z
crossposted on MO: http://mathoverflow.net/questions/70225/planar-graphs-and-skew-binary-spaces
Suresh Venkat
<graph-theory><co.combinatorics>
Planar Graphs and Skew Binary Subspaces
Einoma Kalaintzis
# Planar Graphs and Skew Binary Subspaces

(Asked by: username_0 on 2011-07-12)

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.

**Tags:** graph-theory, co.combinatorics

> **Comments:**
> **username_1**: crossposted on MO: http://mathoverflow.net/questions/70225/planar-graphs-and-skew-binary-spaces  

---

## 1 answers

### Answer by username_0 on 2011-07-14. Score: 1

The question has been resolved by Chris Godsil on [Maths Overflow](https://mathoverflow.net/questions/70225/planar-graphs-and-skew-binary-spaces). 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.

> **Comments:**
> **username_1**: 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  

---

