Linear Algebraic Proof of Eulerian Circuits

Question

A standard proof of the existence of Eulerian circuits proves the following are equivalent for a connected graph $G$:

(i) Every vertex in $G$ has even degree

(ii) The edges of $G$ can be partitioned into disjoint cycles

(iii) $G$ is Eulerian

I'm interested in $(i) \implies (ii)$. The proof I've seen is by induction. However, the claim is very much about the edge space of $G$. Is there a linear algebraic proof of that implication?

Answer 1

The generalization is an Eulerian matroid

An Eulerian matroid is a matroid whose elements can be partitioned into a collection of disjoint circuits. ... Eulerian matroids were defined by Welsh (1969) as a generalization of the Eulerian graphs. ... The graphic matroids of Eulerian graphs are examples of Eulerian matroids.

Since you want an analogous theorem for (i) => (ii), the first one has to be rephrased into a statement about edges and circuits; we can't handle vertices and degree in the matroid setting.

Wilde (1975) observes that the graphs that have Euler tours can be characterized in an alternative way that generalizes to matroids: a graph G has an Euler tour if and only if it can be formed from some other graph H, and a cycle C in H, by contracting the edges of H that do not belong to C. In the contracted graph, C generally stops being a simple cycle and becomes instead an Euler tour.

And now we're all set to translate that to a statement about matroids:

Analogously, Wilde considers the matroids that can be formed from a larger matroid by contracting the elements that do not belong to some particular circuit.

Unfortunately this does not characterize Eulerian matroids, but Wilde rescues the theorem in a smaller setting:

He shows that this property is trivial for general matroids (it implies only that each element belongs to at least one circuit) but can be used to characterize the Eulerian matroids among the binary matroids, matroids representable over GF(2): a binary matroid is Eulerian if and only if it is the contraction of another binary matroid onto a circuit.

All from: https://en.m.wikipedia.org/wiki/Eulerian_matroid

The theorem is in: Wilde, P. J. (1975), "The Euler circuit theorem for binary matroids", Journal of Combinatorial Theory.