# Theorems proved using combinatorial nullstellensatz that have no other known proof

Alon's (or Alon and Tarsi's?) combinatorial nullstellensatz is a powerful algebraic tool with many applications in combinatorics and number theory. See this, this, this and this mathoverflow question.

I am looking for good examples of results that were proved using combinatorial nullstellensatz (or its generalisation) but have no other known proof.

• You can start with the 3-choosability of bipartite planar graphs. I don't know of any other proof (but maybe nobody looked for such a proof since the Alon Tarsi paper) – Louis Esperet Jun 9 '15 at 13:21
• @Louis: Thanks. That looks like a good candidate. – Anurag Jun 9 '15 at 14:04
• @LouisEsperet if I am not mistaken, there exists a combinatorial proof using the kernel technique (for all bipartite graphs with outdegrees at most $m$ and coloring with $m+1$ colors.) – Fedor Petrov Mar 20 at 9:04
• You're completely right, thank you. – Louis Esperet Mar 20 at 10:30

Let $$G$$ be a $$d$$-degenerate graph (i.e. each subgraph contains a vertex of degree at most $$d$$). A classical result in graph theory is that if each vertex is given a list of $$d+1$$ colors, then every vertex can choose a color from its list such that the resulting coloring is proper.
Now, assume instead that each vertex of $$G$$ is given a list of size $$d+1$$ colors, except one vertex which has a list of size $$d$$. It can be proved with the combinatorial nullstellensatz that in this case again, each vertex can be colored with a color from its list, such that the resulting coloring of $$G$$ is proper (see the paper above, where a stronger result is proved when $$d+1$$ is prime, but the proof actually works in the weaker setting for general $$d$$).