A flow<\/em> on a graph is an assignment to each edge of of a direction and a non-negative integer (the flow in that edge) such that the flows into and out of each vertex agree. \u00a0A flow is nowhere zero<\/em> if every edge is carrying a positive flow and (confusingly)\u00a0it\u00a0is a -flow if the flows on each edge are all less than .\u00a0 Tutte\u00a0conjectured that every bridgeless graph has a nowhere zero -flow (so the possible flow values are ). \u00a0This is supposed to be a generalisation of the -colour theorem. \u00a0Given a plane graph and a proper colouring of its faces by ,\u00a0push flows of value anticlockwise around each face of . \u00a0Adding the flows in the obvious way gives a flow on in which each edge has a total flow of in some direction.<\/p>\n

Seymour proved that every bridgeless graph has a nowhere zero -flow. \u00a0Thomas Bloom<\/a> and I worked this out at the\u00a0blackboard, and I want to record the ideas here. \u00a0First, a folklore observation that a minimal counterexample must be\u00a0cubic and -connected.\u00a0 We will temporarily allow graphs to have loops and multiple edges.<\/p>\n

We first show that is -edge-connected. \u00a0It is certainly -edge-connected, else there is a bridge. \u00a0(If is not even connected then look at a component.) \u00a0If it were only -edge-connected then the graph would look like this.<\/p>\n

<\/p>\n

 <\/p>\n

Contract the top cross edge.<\/p>\n

<\/p>\n

If the new graph has a nowhere zero -flow then so will the old one, as the flow in the bottom cross edge tells us\u00a0how much flow is\u00a0passing between the left and right blobs at the identified vertices and so the flow the we must put on the edge we contracted. \u00a0So is -edge connected.<\/p>\n

Next we show that is -regular. \u00a0A vertex of degree forces a bridge; a vertex of degree forces the incident edges to have equal flows, so the two edges can be regarded as one. \u00a0So suppose there is a vertex of degree at least .<\/p>\n

<\/p>\n

We want to replace two edges and by a single edge to obtain a smaller graph that is no easier to find a flow for. \u00a0The problem is that in doing so we might produce a bridge.<\/p>\n

The -edge-connected components of \u00a0 are connected by single edges in a forest-like fashion. \u00a0If any of the leaves of this forest contains only one neighbour of then there is a -edge-cut, so each leaf contains at least two neighbours of .<\/p>\n

<\/p>\n

If there is a component of the forest with two leaves then choose and to be neighbours of from different leaves of that component.<\/p>\n

<\/p>\n

Otherwise the -edge-connected components of are disconnected from each other. \u00a0Now any such component must contain at least neighbours of , else there is a -edge-cut. \u00a0If some contains neighbours of then we can choose and to be any two of them. \u00a0Otherwise all such contain exactly neighbours of , in which case\u00a0there must be at least two of them and we can choose and to be neighbours of in different components.<\/p>\n

<\/p>\n

So is -regular and -edge-connected. \u00a0If is only -connected then there is no flow between -connected components, so one of the components is a smaller graph with no nowhere zero -flow. \u00a0If is only -connected then because is so small we can also find a -edge-cut.<\/p>\n

<\/p>\n

Finally, we want to get rid of any loops and multiple edges we might have introduced. \u00a0But loops make literally no interesting contribution to flows and double edges all look like<\/p>\n

<\/p>\n

and the total flow\u00a0on the pair just has to\u00a0agree with the edges on either side.<\/p>\n

We’ll also need one piece of magic (see postscript).<\/p>\n

Theorem.<\/strong> (Tutte) Given any integer flow of there is a -flow of that agrees with the original flow mod . \u00a0(By definition, flows of in one direction and in the other direction agree mod .)<\/em><\/p>\n

So we only need to worry about keeping things non-zero\u00a0mod .<\/p>\n

The engine of Seymour’s proof is the following observation.<\/p>\n

Claim.<\/strong>\u00a0Suppose that where each is a cycle and the number of new edges when we add to is at most . \u00a0Then has a -flow which is non-zero outside . \u00a0<\/em><\/p>\n

Write for the set of edges added at the th stage. \u00a0We assign flows to in that order. \u00a0Assign a flow of in an arbitrary direction to\u00a0; now the edges in have non-zero flow and will never be touched again. \u00a0At the next stage, the edges in might already have some flow; but since there are only two possible values for these flows mod . \u00a0So there is some choice of flow we can put on to ensure that the flows on are non-zero. \u00a0Keep going to obtain the desired -flow, applying Tutte’s result as required to bring values back in range.<\/p>\n

Finally, we claim that the we are considering have the above form with being a vertex disjoint union of cycles. \u00a0Then trivially has a -flow, and times this -flow plus the -flow constructed above is a nowhere-zero -flow on .<\/p>\n

For , write for the largest subgraph of that can be obtained as above by adding cycles in turn, using at most two new edges at each stage. \u00a0Let be a maximal collection of vertex disjoint cycles in with connected, and let . \u00a0We claim that is empty. \u00a0If not, then the -connected blocks of are connected in a forest-like fashion; let be one of the leaves.<\/p>\n

<\/p>\n

By -connectedness there are three vertex disjoint paths from to . At most one of these paths travels through ; let and be endpoints of two\u00a0paths that do not.\u00a0 These\u00a0paths must in fact be single edges, as the only other way to get to would be to travel through . \u00a0Finally, since is -connected it contains\u00a0a cycle through and , contradicting the choice of .<\/p>\n

Postscript. <\/strong>It turns out that Tutte’s result is far from magical; in fact its proof is exactly what it should be. \u00a0Obtain a directed graph from by forgetting about the magnitude of flow in each edge (if an edge contains zero flow then delete it). \u00a0We claim that every edge is in a directed cycle.<\/p>\n

<\/p>\n

Indeed, choose a directed edge . \u00a0Let be the set of vertices that can be reached by a directed path from and let be the set of vertices that can reach by following a directed path. \u00a0If\u00a0 is not in any directed cycle then and are disjoint and there is no directed path from to . \u00a0But then there can be no flow in\u00a0, contradicting the definition of .<\/p>\n

So as long as there are edges with flow value at least , find a directed cycle containing one of those edges and push a flow of through it in the opposite direction. \u00a0The total flow in edges with flow at least strictly decreases, so we eventually obtain a -flow.<\/p>\n","protected":false},"excerpt":{"rendered":"

A flow on a graph is an assignment to each edge of of a direction and a non-negative integer (the flow in that edge) such that the flows into and out of each vertex agree. \u00a0A flow is nowhere zero if every edge is carrying a positive flow and (confusingly)\u00a0it\u00a0is a -flow if the flows … <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[4],"tags":[8,12,17,25],"_links":{"self":[{"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/posts\/120"}],"collection":[{"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/comments?post=120"}],"version-history":[{"count":0,"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/posts\/120\/revisions"}],"wp:attachment":[{"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/media?parent=120"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/categories?post=120"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/tags?post=120"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}