# Which paths in a graph are orthogonal to all cycles?

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:

[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.]

• What do you mean by "embedded"? – darij grinberg May 13 '16 at 6:36
• Also, I don't get the second boldfaced question. If your digraph is a directed $2m$-cycle, and $c (\gamma)$ is the alternating sum of the arcs of this cycle (i.e., sum of all even arcs minus sum of all odd arcs), then isn't $c (\gamma)=0$? Or do you mean $\partial(c (\gamma)) =0$? – darij grinberg May 13 '16 at 6:41
• I think that the alternating sum you mentioned isn't a path, since the vertices don't line up as specified by Baez's definition, @darijgrinberg. Say $m=2$ and the cycle has edges $abcd$. You're proposing $ab^{-1}cd^{-1}$ but (writing $s$ and $t$ for source and target), $s(b^{-1}) = t(b) \neq t(a)$. (And I promise I'm not stalking you, the other notification is just a coincidence. ;)) – Omar Antolín-Camarena May 13 '16 at 20:09
• @OmarAntolín-Camarena: Ah! I misunderstood the definition of a path indeed. – darij grinberg May 13 '16 at 20:28

$\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$

• Dumb question: you say " For any vertex $w$ of $U$ other than $u$, the harmonic property $(\ast)$ forces..." But you're only asserting $(\ast)$ for vertices other than than $u$ and $v$. What about $v$? (I have not attempted to actually think about this yet.) – John Baez May 9 '16 at 20:45
• Yes, the inequality points the right way at $v$. I should edit to make this clearer but I'll just write it here: for $w \neq u$, $v$, the value $n_w$ is the average of its neighbors so, if $n_w$ is the maximum $M$ then $n_x=M$ for all $x \sim w$. At $v$, the value $n_v$ is less than the average of the neighbors, so $n_v$ simply can't be maximal. – David E Speyer May 9 '16 at 21:19
• I think a bit of fine print is needed to explain why $u \in U$. If $M$ is achieved at some vertex $m$, $U$ will "spread" to all vertices for which there is a path from $m$ that doesn't pass through $u$ or $v$. It might be that every path from $m$ to $u$ passes through $v$ (this need not contradict the no-bridge condition). But then $v$ will have a neighbour in $U$, and $(\ast)$ will force $v \in U$, contradicting $(\ddagger)$ which forces $v \notin U$. – Greg Egan May 10 '16 at 1:06
• If $u \not \in U$, then there are no edges from $U$ to the rest of $\Gamma$, violating that $\Gamma$ is connected. But I agree that I should improve the writing. – David E Speyer May 10 '16 at 1:43
• If $\Gamma - \{v\}$ is not connected, I don't think it follows from $\Gamma$ itself being connected that $u \in U$, since (at first glance) $U$ could be confined to the component of $\Gamma - \{v\}$ that does not contain $u$. That can easily be shown to lead to a contradiction about $v$, but I think that small extra argument is necessary. – Greg Egan May 10 '16 at 4:17

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$.

• I like the idea of this proof, but I don't see how to make it rigorous. If a path $p$ is not simple it contains a cycle $c$, but we don't always have $\langle c, p \rangle = |c|$, and indeed we can have $\langle c, p \rangle = 0.$ There are various kinds of counterexamples: here's one. Suppose $p = a b c b^{-1} c^{-1}$ where $b, c$ are cycles that start and end at the same point but share no edges, and $a$ is path sharing no edges with $b$ or $c$. Then $p$ is not simple, and it contains a cycle $c$, but $\langle p, c \rangle = 0$. – John Baez May 8 '16 at 21:09
• Just follow the path (starting from the first vertex) until you come to some vertex for the second time. The segment of the path between two visits is a <i>simple</i> cycle for which the claim holds. – Ilya Bogdanov May 10 '16 at 10:35
• Applying Ilya's prescription to John's example would identify $b$ as the simple cycle of choice. But $\langle p,b \rangle=0$. – Greg Egan May 10 '16 at 11:19
• .I see your point. I've tried to rewrite this part; is it better now? – Ilya Bogdanov May 12 '16 at 15:56
• You say "Take the multiset of all edges of γ; if it contains a pair of inverse edges, remove it, and repeat this while possible". Suppose I have a path like $e_1 e_2 e_3 e_4 e_2^{-1}$ where $e_1: v_1 \to v_2$, $e_2: v_2 \to v_3$, $e_3: v_3 \to v_4$, $e_4: v_4 \to v_3$. There is a pair of inverse edges in this path, but if I try to remove them, I get $e_1 e_3 e_4$ which is not a well-defined path, since $e_3$ doesn't start where $e_1$ ends. – John Baez May 14 '16 at 18:14

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$$