Let $\Gamma$ be an oriented graph (multiple edges between vertices are allowed), and let $G$ be a finite abelian group. We define $H_1(\Gamma,G)$ to be the set of $G$-linear combinations of edges of $\Gamma$ such that the oriented sum at every vertex is zero. My question is the following: under what conditions on $\Gamma$ does there exist an element $\eta\in H_1(\Gamma,G)$ that is nonzero on every edge?

I am primarily interested in the case $G=\mathbb{Z}/p\mathbb{Z}$ for $p$ prime. I can make a number of simple observations:

1) $\Gamma$ cannot contain a bridge edge. Hence $\Gamma$ has no vertices of valency one, and it is clear that we can remove all vertices of valency two, so we can assume that all vertices have valency at least three.

2) In the simplest case $G=\mathbb{Z}/2\mathbb{Z}$, a necessary and sufficient condition is that each vertex of $\Gamma$ has even valency.

3) By a counting argument, such an element $\eta$ exists for any fixed $\Gamma$ without bridge edges if $p$ is sufficiently large (specifically, if $p\geq 3b_1(\Gamma)-3$). Indeed, $H_1(\Gamma,\mathbb{Z}/p\mathbb{Z})$ is a vector space over $\mathbb{Z}/p\mathbb{Z}$ of dimension $b_1(\Gamma)$; for each edge $e$ the set $H_e$ of elements of $H_1(\Gamma,\mathbb{Z}/p\mathbb{Z})$ that vanish on $e$ is a hyperplane; if $\Gamma$ has no edges of valency one or two then the number of edges is at most $3b_1(\Gamma)-3$; so the union of these hyperplanes $H_e$ cannot be all of $H_1(\Gamma,\mathbb{Z}/p\mathbb{Z})$ if $p\geq 3b_1(\Gamma)-3$.

4) Let $\Gamma$ be the graph obtained from $K_{3,3}$ by adding two vertices on different edges, and joining them by a new edge. A brute-force count reveals that there is no $\eta\in H_1(\Gamma,\mathbb{Z}/3\mathbb{Z})$ which is everywhere nonzero. Hence assuming that $\Gamma$ has no bridges is not enough (at least for $p=3$).

5) If $\Gamma$ is planar, then the four-color theorem implies that such an element exists in $H_1(\Gamma,\mathbb{Z}/p\mathbb{Z})$ for all $p\geq 7$: take a basis of cycles corresponding to the faces, oriented clockwise; label them with 0,1,2,3 such that no cycles intersecting the boundary are labeled 0; the resulting sum is nonzero mod $p$ on every edge for any $p\geq 7$.

I have looked at a number of papers on group-labeled graphs and biased graphs (which I believe is the terminology for this problem), but I can't tell if anyone has considered this specific question. I would appreciate any references for this problem.


1 Answer 1


The terminology you are looking for is Nowhere-Zero Flow. It is actually known that these exist on any bridgeless graph for any $\mathbb Z/n\mathbb Z$ with $n\geq 6$. One of the biggest problems in the field is to prove that you can actually take $n=5$.

  • 1
    $\begingroup$ Thanks, that's exactly what I'm looking for! $\endgroup$ Jun 19, 2019 at 17:34
  • $\begingroup$ so, does nowhere zero flow imply 1-factorizability in the case of simple undirected graphs, or, does te converse assumption hold? $\endgroup$
    – vidyarthi
    Jun 21, 2019 at 17:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.