Petersen graph does not have a nowhere-zero 4-flow

Question

I try to prove that the Petersen graph does not have a nowhere-zero 4-flow (i.e., over $\mathbb{Z}_4$), but I don't know how a proof could work...

I'm happy about every hint, thank you in advance!

Answer 1

Here is Tutte polynomial of Petersen graph

$$x^9 + 6x^8 + 21x^7 + 56x^6 + 12x^5y + y^6 + 114x^5 + 70x^4y + 30x^3y^2 + 15x^2y^3 + 10xy^4 + 9y^5 + 170x^4 + 170x^3y + 105x^2y^2 + 65xy^3 + 35y^4 + 180x^3 + 240x^2y + 171xy^2 + 75y^3 + 120x^2 + 168xy + 84y^2 + 36x + 36y.$$

Put $x=0,y=-3$, you get 0: indeed, $$y^6 + 9 y^5 + 35 y^4 + 75 y^3 + 84 y^2 + 36 y=y (y + 1) (y + 2) (y + 3) (y^2 + 3 y + 6).$$ Thus, there is no nowhere zero 4-flow.

Tutte polynomial may be found by brute force applying deletion-contraction recurrence. Since you care only about flows, you may ignore all terms which contain $x$, this makes calculation slightly shorter.

If you want a less boring and more instructive proof, you may start with observation that the edges with flow value 2 must form a perfect matching, and after removing this perfect matching you should get a collection of even cycles (for an odd cycle, you can not extend a flow to it). Since Petersen graph does not have cycles of length less than 5, this is only possible if you get a one cycle of length 10 (Hamiltonian cycle). But such a cycle also does not exist: it is easy to see that if you add 5 disjoint edges to a cycle of length 10 you always get a cycle of length less than 5.