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.

13more comments