# Co-trees of a simple graph

Consider fundamental cycles (say $$k$$ of them) of a specific spanning tree of a simple graph (with $$m$$ edges) which is also connected and has no one-edge bonds.

Make the graph directed (in an arbitrary way) and each cycle directed (to follow consistently one of the two possible orientations); then create a matrix C with $$k$$ rows and $$m$$ columns whose elements indicate whether an edge is a part of the cycle (by $$1$$ or $$-1$$ when the two orientations agree or not, respectively) or not (by 0).

How would one prove the following:

Selecting $$k$$ columns of the matrix, the corresponding sub-determinant equals to $$1$$ or $$-1$$ when the corresponding edges contain no bond, equals to 0 otherwise.

A bit more challenging would be to prove that C is totally unimodular.

(My original contention that there was a unique bijection between edges of a cotree and fundamental cycles a potentially different spanning tree has been disproved below).

• I am sorry, the previous (and accepted) answer was wrong in one direction. Actually the claim simply does not hold: if the bijection exists, it may be not a cotree. Apr 27 at 7:05
• well, i see. Then it remains to do two things: prove the uniqueness when $S$ is a cotree; prove that $S$ is a cotree when the bijections exists and is unique. Apr 28 at 13:30
• hm, it looks that it is not always unique, please check my example Apr 28 at 19:59
• I added the proof of total unimodularity May 2 at 8:27
• Edge $e$ which goes from $u$ to $v$ correspinds to $v-u$. This extends to an isomorphism between the span of edges of a tree and the hyperplane "sum of coordinates equals 0" in the span of vertices. May 3 at 6:21

## 2 Answers

Fix a spanning tree $$T\subset E$$ in a connected graph $$G=(V,E)$$. It defines fundamental cycles $$C_1,\ldots,C_k$$, $$k=|E|-|T|$$: for any $$e\in E\setminus T$$ take the unique cycle in $$T\cup \{e\}$$.

Let first $$k$$ columns of C correspond to the edges in $$E\setminus T$$. Then the first $$k$$ columns form a matrix with $$\pm 1$$ on the diagonal and zeros outside the diagonal. Consider an $$r\times r$$ minor of C, we should prove that it either 0 or $$\pm 1$$. By the structure of the first $$k$$ columns, this reduces to the case when all $$r$$ columns of the minor correspond to $$r$$ edges $$e_1,\ldots,e_r$$ of a tree, let $$r$$ its rows correspond to $$f_1,\ldots,f_r$$ of $$E\setminus T$$. We contract all edges of $$T$$ except $$e_1,\ldots,e_r$$. I claim that if the set $$f_1,\ldots,f_r$$ does not contain a cycle, the corresponding rows are linearly independent over any field (thus the minor is $$\pm 1$$), and if they do contain a cycle, the rows are dependent with the coefficients $$\pm 1$$ (thus the minor is 0). For seeing this, we embed the span of the edges $$e_1,\ldots,e_r$$ to the hyperplane in the vertex space of the (new) tree $$\tilde{T}$$: each edge $$e_i=uv$$ corresponds to the vector $$v-u$$. With this embedding, the row which correspond to edge $$f_j=uv$$ corresponds to $$\pm(v-u)$$. The above claim is now clear.

Below is a couple of claims concerning the previous version of the question.

We have the following

Theorem 1. If set $$S\subset E$$ is a cotree (a complement of a spanning tree), then there exists a bijection $$f\colon S\to \{1,\ldots,k\}$$ such that $$e\in C_{f(e)}$$ for all $$e\in S$$.

Proof. To prove that such a bijection exists, by Hall lemma (for the natural bipartite graph with parts $$S$$ and $$\{1,\ldots,k\}$$ corresponding to a relation $$(e,i):e\in C_i$$) it suffices to prove that the union $$C_0$$ of any $$m=1,2,\ldots,k$$ fundamental cycles contain at least $$m$$ elements of $$S$$. Denote $$T_0=T\cap C_0$$. Then $$T_0$$ is a forest, and it is an inclusion-maximal subforest of $$C_0$$ (since after adding to $$T_0$$any edge in $$C_0\setminus T$$ you get a fundamental cycle). Assume that on the contrary $$|S\cap C_0|\leqslant m-1$$, this is equivalent to $$|(E\setminus S)\cap C_0|\geqslant |C_0|-m+1=r+1$$. But $$E\setminus S$$ is a tree, then $$(E\setminus S)\cap C_0$$ is a subforest of $$C_0$$, and it has more edges than an inclusion-maximal subforest $$T_0$$ of $$C_0$$. A contradiction.

The converse does not hold. For example, consider the graph (the black edges constitute a spanning tree, take the edge $$e_1$$ in the fundamental cycle $$C_1$$ and $$e_2$$ in $$C_2$$. The set $$\{e_1,e_2\}$$ is not a cotree, however.)

Also, the bijection is not always unique. (the spanning tree is black) three edges $$e_1,e_2,e_3$$ may be paired with fundamental cycles by different ways.

Finally, I prove

Theorem 2. Assume that set $$S\subset E$$ is such that there exists unique bijection $$f\colon S\to \{1,\ldots,k\}$$ such that $$e\in C_{f(e)}$$ for all $$e\in S$$. Then $$S$$ is a cotree.

Proof. Consider the cut matroid of $$G$$: the bases are cotrees, the independent sets are subsets of cotrees. Let $$e_1,\ldots,e_k$$ be all elements of $$E\setminus T$$ enumerated so that $$e_i\in C_i$$. Note that $$f\in C_i$$ if and only if $$(T\cup e_i)\setminus f$$ is a tree, that is, $$((E\setminus T)\setminus e_i)\cup f=f\cup \{e_j:j\ne i\}$$ is a cotree. That is, if $$f$$ does not belong to a flat generated by $$\{e_j:j\ne i\}$$. Our matroid is a vector matroid, so this may be said as "the coefficient of $$e_i$$ in the expansion of $$f$$ in the basis $$\{e_1,\ldots,e_k\}$$ is non-zero". That is, we are given that the matrix of vectors of $$S$$ in the basis $$\{e_1,\ldots,e_k\}$$ has unique generalized diagonal with non-zero elements. This yields that the determinant of this matrix is non-zero, so, it is non-singular and $$S$$ constitutes a basis.

Consider 2 different spanning trees of the graph, and the corresponding cotrees and fundamental cycles. Then $$C_2=C_2|S_1*C_1$$ spells out the algebraic details of the following well-known fact: every fundamental cycle of Type 2 is a linear combination of fundamental cycles of Type 1 with coefficients from the $${0,1,-1}$$ set; $$C_2|S_1$$ implies selecting only those columns/edges of $$C_2$$ which are in the first cotree (these are the coefficients of the linear combinations).

Now, selecting only columns which are in $$S_2$$ from each side of this equation yields $$C_2|S_2=C_2|S_1*C_1|S_2$$ Since the determinant of the LHS matrix is equal to either $$1$$ or $$-1$$ (there is exactly one way of matching each edge of a cotree with the corresponding fundamental cycle, only one of the $$k!$$ term of the determinant is non-zero). This implies that (integer-valued) determinants of each of the RHS matrices have the same property (being equal to $$1$$ or $$-1$$).

When the $$k$$ edges contain a bond, there is a linear combination of the corresponding columns of C (with coefficients from the $$1,-1$$ set) which yields a zero vector (a bond has to be traversed both ways by each cycle - the two contributions always cancel). This implies that these columns are linearly dependent and the corresponding determinant is thus equal to $$0$$.

The totally unimodular issue: It's know (and I take it for granted) that C is unimodular if and only if it's possible to find a linear combination of any selection of its rows such that (i) the coefficients are either $$1$$ or $$-1$$, (ii) the resulting elements are all from the $$0,1,-1$$ set.

To find such coefficients, one must first simply add the selected rows and apply 'mod 2' to each component of the answer (getting a vector of ones and zeros); this defines an undirected closed trail (revisiting vertices is allowed). Give this trail a consistent orientation (there may be several ways of doing it) by changing the sign of some of the $$1$$ components; the corresponding sign of the unique co-tree component of each row of C tells us whether the row should be added or subtracted - the answer will match the already constructed directed trail.