Which paths in a graph are orthogonal to all cycles?

Question

Start with some standard stuff. Suppose we have a directed graph $\Gamma$. I'll write $e : v \to w \,$ when $e$ is an edge going from the vertex $v$ to the vertex $w$. We get a vector space of 0-chains $C_0(\Gamma,\mathbb{R})$, which are formal linear combinations of vertices, and a vector space of 1-chains $C_1(\Gamma,\mathbb{R})$, which are formal linear combinations of edges. We get a boundary operator

$$ \partial : C_1(\Gamma,\mathbb{Z}) \to C_0(\Gamma,\mathbb{Z}) $$

sending each edge $e: v \to w$ to the difference $w - v$. A 1-cycle is a 1-chain $c$ with $\partial c = 0$. There is an inner product on 1-chains for which the edges form an orthonormal basis.

Any path in the graph gives a 1-chain. When is this 1-chain orthogonal to all 1-cycles?

To make this interesting, I need to rule out some obvious possibilities. If we have a graph consisting of two triangles connected by an edge, the path consisting of that one edge will be orthogonal to all 1-cycles:

To rule out this sort of situation, let's suppose $\Gamma$ has no bridges, meaning edges whose removal increases the number of connected components. The edge with the arrow on it in the picture above is a bridge.

Question: Suppose $\Gamma$ is a graph with no bridges. Any path in such an embedded graph gives a 1-chain. If this 1-chain is orthogonal to all 1-cycles, must it vanish?

To make this precise: I'm defining a path $\gamma$ to be a finite sequence of edges $e : v \to w$ and their formal 'inverses' $e^{-1}: w \to v$, like this:

$$ e_1^{\pm} : v_0 \to v_1, $$ $$ e_2^{\pm} : v_1 \to v_2 , $$ $$ \dots $$ $$ e_n^{\pm} : v_{n-1} \to v_n .$$

The corresponding chain is

$$ c(\gamma) = \pm e_1 \pm e_2 \pm \; \cdots \;\pm e_m. $$

Question: If $\Gamma$ is a graph with no bridges, and $\gamma$ is a path in $\Gamma$ such that the inner product of $c(\gamma)$ with every cycle vanishes, must we have $c(\gamma) = 0$?

I believe someone should have settled this by now, since it sounds easy, and the space of 1-chains orthogonal to all cycles has been studied quite a lot: it's called the cut space of the graph.

A cut is a partition of the vertices of a graph into two disjoint subsets. Any cut determines a cut-set, the set of edges that have one endpoint in each subset of the partition. If we take the sum of all those edges, we get a 1-chain orthogonal to all cycles. It's known that the cut space is spanned by 1-chains coming from cuts in this way. For example, in the graph I drew, the edge with the arrow on it spans the cut space.

A proof can be found here:

• Norman Biggs, Algebraic Graph Theory.

but I suspect there's a lot more known about this subject!

[Note: I have edited my original question to simplify the hypotheses, and also called elements of $Z_1(\Gamma,\mathbb{R})$ 1-cycles, to distinguish them from cycles in the sense of graph theory.]

Answer 1

$\def\ZZ{\mathbb{Z}}$The answer to the boldfaced question is yes. Let $\Gamma$ be a connected graph with no cut edges. We will show that, if $\gamma \in C_1(\Gamma, \ZZ)$ with $\partial \gamma$ of the form $[u] - [v]$ and $\langle \gamma, \delta \rangle =0$ for all $\delta \in \mathrm{Ker}(\partial: C_1 \to C_0)$, then $\gamma=0$. We write $x \sim y$ to express that vertices $x$ and $y$ of $\Gamma$ are neighbors.

Proof: If $u=v$ then we have $\langle \gamma, \gamma \rangle =0$ so $\gamma=0$, as previously noted. So we may assume $u \neq v$.

For any vertex $w \in \Gamma$, let $D(w) = \sum_{x \sim w} [w \to x] \in C_1(\Gamma, \ZZ)$. The $D(w)$ form an integer spanning set for the cut space. (If $H$ is any subset of the vertices, then the vector associated to $H$ is $\sum_{w \in H} D(w)$.) So $\gamma = \sum_w n_w D(w)$ for some integers $n_w$. We thus have $$\partial \gamma = \sum_w n_w \left(d_w [w] - \sum_{x \sim w} [x] \right) = [u] - [v]$$ where $d_w$ is the degree of $w$.

For every vertex $w$ other than $u$ and $v$, we deduce $$d_w n_w = \sum_{x \sim w} n_x. \quad (\ast)$$ In other words, $n_w$ is the average of $n$ on the neighbors of $w$. (Conceptually, $n$ is "harmonic" away from $u$ and $v$.) Similarly, $$d_u n_u = \sum_{x \sim u} n_x+1 \quad (\dagger)$$ and $$d_v n_v = \sum_{x \sim v} n_x-1 \quad (\ddagger)$$

Let $M$ be the largest values of $n_w$ at any vertex $w$ of $\Gamma$ and let $U$ be the set of vertices where $n_w = M$. It follows from equation $(\ddagger)$ that $v \notin U$, so $U$ is not all of $\Gamma$.

For any vertex $w$ of $U$ other than $u$, the harmonic property $(\ast)$ forces all neighbors of $w$ to also be in $U$. So, if $u \not\in U$, then $U$ is a proper connected component of $\Gamma$, a contradiction.

We now know that $u \in U$, and only $u$ can border vertices of $\Gamma$ outside of $U$. And equation $(\dagger)$ forces $u$ to have a single neighbor $u'$ not in $U$, with $n_{u'}=n_u-1$.

But then $u \to u'$ is a cut edge separating off the component $U$, a contradiction. $\square$

Answer 2

EDIT Take te multiset of all edges of $\gamma$; if it contains a pair of inverse edges, remove it, and repeat this while possible. If the resulting multiset is empty, then $c(\gamma)=0$, otherwise we will find a cycle with nonzero product with $\gamma$.

Now each edge appears in only one direction, the in-degree and out-degree of each vertex with respect to this multiset are equal, except for $v_0$ and $v_n$ (if they are distinct). If this multiset contains a subset which forms a cycle $C$, then $\langle \gamma, C\rangle=|C|>0$. Otherwise, let us move along the edges from $v_0$, not passing any edge twice. We either come twice to some vertex (thus finding a cycle), or finish at $v_n$. In the latter case, we have passed all the edges (otherwise the remaining ones form a cycle again).END OF EDIT

Thus we may assume that $\gamma$ is simple, so $\gamma$ has the form $v_0\to v_1\to\dots\to v_n$ with $v_0,v_1,\dots,v_n$ distinct.

Let $G$ be the underlying (undirected) graph of our initial graph. Let $G'$ be the subgraph of graph $G$ obtained by removing the edges (not vertices!) of $\gamma$. If the component of $v_n$ in $G'$ contains no other $v_i$, then the edge $(v_{n-1},v_n)$ is a bridge in $G$, so this edge contradicts the condition imposed on the faces. Thus there exists a path in $G'$ from $v_n$ to $v_i$ for some $i$. This path, augmented by $v_i\to v_{i+1}\to\dots\to v_n$, provides a cycle having a positive product with $\gamma$.

Answer 3

This answer is an attempt to slightly rephrase Ilya's argument; I would have written it as a comment, but there's not enough room.

Given a path $\gamma$ with endpoints $v_0$ and $v_n$, we have a 1-chain $c(\gamma)$, which is an integer-linear combination of edges of the graph. Let $E_{c(\gamma)}$ be the set of edges with non-zero coefficients in $c(\gamma)$; this need not include every edge that appears in the path, since some might cancel to zero in the 1-chain. If we think of these edges as decorated with the integer coefficients they inherit from the 1-chain $c(\gamma)$, we can associate a 1-chain with any subset of $E_{c(\gamma)}$.

It's possible that $E_{c(\gamma)}$ as a subgraph of $\Gamma$ contains several connected components that share no vertices with each other, but since the boundary of $c(\gamma)$ is only non-zero on $v_0$ and $v_n$, and it's impossible for a 1-chain to have a single-point boundary, these components would need to include exactly one whose 1-chain's boundary was non-zero on $v_0$ and $v_n$, and all the rest would have to give 1-cycles. Since they're all disjoint, any one of the 1-cycles $\chi$ would satisfy $\langle c(\gamma), \chi \rangle = \langle \chi, \chi \rangle \gt 0$.

Assuming now that $E_{c(\gamma)}$ is connected as a subgraph, we can build up a 1-chain $\sigma$ with a positive inner product with $c(\gamma)$ as follows. Starting at $v_0$, pick an edge $\epsilon_1$ incident on $v_0$, and put $\pm \epsilon_1$ in $\sigma$, with the sign chosen to be the same as the coefficient of $\epsilon_1$ in $c(\gamma)$. Then advance to the other vertex of $\epsilon_1$, and choose an edge $\epsilon_2$ such that $\epsilon_2 \ne \epsilon_1$, and $\pm \epsilon_2$ with the same sign as the coefficient of $\epsilon_2$ in $c(\gamma)$ gives a boundary for $\pm \epsilon_1 \pm \epsilon_2$ that is zero at the current vertex. This must be possible (assuming we haven't ended up at an endpoint of the path), since the boundary of $c(\gamma)$ is zero at the current vertex, so the signs of the edge coefficients in $c(\gamma)$ can't all give boundaries of the same sign here.

We continue this process until we reach either $v_n$, the endpoint of the path, or a vertex we've visited before. If we reach a vertex we've visited before, we can drop any earlier edges from $\sigma$ and obtain a 1-cycle with a positive inner product with $c(\gamma)$.

If we reach $v_n$, there are two possibilities. If $\sigma = c(\gamma)$ then $\sigma$ describes a simple path $\gamma'$ from $v_0$ to $v_n$ with the same 1-chain as our original path, and we can proceed to use that simple path in place of $\gamma$. If $\sigma \ne c(\gamma)$, it nonethless has the same boundary. Since $\sigma$ is supported on a subset of the same edges as $c(\gamma)$, and its coefficients are of the same sign but never greater in magnitude (and must be less on at least one edge), $\langle c(\gamma), \sigma \rangle$ will be strictly less than $\langle c(\gamma), c(\gamma) \rangle$. So we'll have a non-trivial 1-cycle $\ell = c(\gamma) - \sigma$, and:

$$\langle c(\gamma), \ell \rangle = \langle c(\gamma), c(\gamma) \rangle - \langle c(\gamma), \sigma \rangle \gt 0$$

Finally, suppose we have a simple path $\gamma': v_0 \to v_1 \to \dots \to v_n$ with the same 1-chain as $\gamma$. (The following refinement of Ilya's argument is something that John described to me in correspondence.) Since the edge $e_n: v_{n-1} \to v_n$ cannot be a bridge, there must be a path joining $v_n$ to $v_0$ that does not include that $e_n$. If we follow that path only as far as the first of the $v_i$ it reaches, we will have a path $\rho: v_n \to v_i$ which uses no edges of the simple path $\gamma'$. We can then append the portion of $\gamma'$ that goes from $v_i$ to $v_n$, call it $\gamma'_i$, to obtain a 1-cycle $c(\rho) + c(\gamma'_i)$ that must have a positive inner product with $c(\gamma)$:

$$\langle c(\gamma), c(\rho) + c(\gamma'_i) \rangle = \langle c(\gamma'_i), c(\gamma'_i) \rangle \gt 0$$