The Setting
Take a finite directed multigraph , a set of its edges and a value in prescribed on each edge of . The lemma asks when these values are those of a flow over on the whole of , and it answers through the components of the graph left when the edges of are deleted. On the cubic grid of side it also asks how small a component witnessing a failure can be taken, against the size of the grid and against the number of edges in .
Components and Divergence
A finite directed multigraph consists of a finite set of vertices, a finite set of edges and two maps from to that give each edge its tail and its head . Values lie in the field of integers modulo .โฆ
For a set , the edge relation off is the relation on under which a vertex is related to a vertex when some edge has tail and head .โฆ Connectivity off is the equivalence relation on generated by the edge relation off : two vertices are connected off when a path of edges outside , each traversed in either direction, joins them.โฆ A component of , the graph with the edges of deleted, is a class of connectivity off , a nonempty set of vertices, and is its number of vertices.โฆ The component of a vertex is the set of the vertices connected to off .โฆ
The incidence map sends an edge function to its divergence (1)โฆ where is the indicator function of the vertex . A flow on is an edge function with ; the flows form the kernel , written on the cubic grid.
For an assignment of values to the edges of , the edge function equals on and outside , and extends to a flow when some flow has for every . A charge on is a function on its vertices.
The Cubic Grid
A vertex of the cubic grid of side , for a natural number , is a triple of integers in ; the vertex set has elements.โฆ An edge of the grid is a unit segment parallel to a coordinate axis, with its lower endpoint as tail and its upper endpoint as head. An edge along runs from to with โฆ, edges along and raise the second or the third coordinate by one in the same way, and the edge set is the disjoint union of these three families.โฆ The box constant is the real number .โฆ
The Claim
Theorem 1. Let be a finite directed multigraph with vertex set and edge set , and let .
(a) An assignment extends to a flow if and only if (2)โฆ
(b) A charge is the divergence of an edge function that vanishes on if and only if (3)โฆ
(c) Let be a charge with , and suppose some component of has . Then some component of satisfies (4)โฆ
(d) Suppose is the cubic grid of side and an assignment does not extend to a flow. Then some component of satisfies (5)โฆ
In the paper, the result reads: for and , some has if and only if every component of has , with the incidence sign of the vertex on the edge , and if no such exists, some nonempty component with has and .
What Is Checked
The four statements are made over a finite directed multigraph with its tail and head maps, a set of its edges, the field , connectivity off with the edge relation that generates it, the components of with their vertex sets, and the incidence map of (1); (5) is made over the cubic grid of side , its vertices, its edges along the three axes with their tails and heads, and the box constant . About these constructions the library proves that is linear over .