Lesson 3

Optional Problems.

Flow Polynomial.

1. (15 points) Prove that an undirected graph has a nowhere-zero \(2\)-flow if and only if every vertex has even degree.
   Hint:

   Work over \(\mathbb{Z}_{2}\).
2. (15 points) Construct a bridgeless graph that has no nowhere-zero \(4\)-flow.
   Hint:

   As always, Petersen graph is a nice starting point!
3. (20 points) Prove that a cubic graph has a nowhere-zero \(3\)-flow if and only if it is bipartite.
   Hint:

   Work over \(\mathbb{Z}_{3}\). If there is an odd cycle, look at the values of its edges in cyclic order.
4. (20 points) Prove that for every integer \(n\ge 3\), the complete graph \(K_{2n}\) has a nowhere-zero \(3\)-flow but has no nowhere-zero \(2\)-flow.
5. (20 points) Prove that if \(G\) is a \(4\)-regular graph, then \(\Phi_{G}(3)\) is equal to the number of orientations of \(G\) in which every vertex has indegree \(2\) and outdegree \(2\) (an Eulerian orientation).