[proofplan] Fix an arbitrary field $k$ and construct a matrix over $k$ whose columns are indexed by the edges of $G$. After choosing an orientation of every non-loop edge, use the oriented vertex-edge incidence matrix, and assign the zero column to each loop. We prove that a set of edge columns is linearly independent exactly when the corresponding edge set is a forest: cycles give explicit signed column dependences, while forests are handled by repeatedly using a leaf vertex to force one coefficient at a time to vanish. Since the construction works over an arbitrary field, $M(G)$ is representable over every field and is therefore regular. [/proofplan] [step:Construct the oriented incidence representation over an arbitrary field] Let $G = (V,E)$ be a finite graph, where loops and parallel edges are allowed. Let $k$ be an arbitrary field. Choose an orientation of each non-loop edge $e \in E$; thus if $e$ is not a loop, it has a tail vertex $t(e) \in V$ and a head vertex $h(e) \in V$ with $t(e) \neq h(e)$. Define the $k$-[vector space](/page/Vector%20Space) $k^V$ to be the set of functions $V \to k$, and define the $k$-vector space $k^E$ to be the set of functions $E \to k$. For each edge $e \in E$, define a column vector $a_e \in k^V$ as follows. If $e$ is a non-loop edge, then \begin{align*} a_e(v) = \begin{cases} 1_k, & v = h(e), -1_k, & v = t(e), 0_k, & v \notin \{h(e),t(e)\}. \end{cases} \end{align*} If $e$ is a loop, define $a_e = 0 \in k^V$. Let \begin{align*} A_k: k^E \to k^V \end{align*} be the [linear map](/page/Linear%20Map) whose value on the standard basis vector corresponding to $e \in E$ is $a_e$. Equivalently, $A_k$ is the oriented incidence matrix of $G$ over $k$, with zero columns for loops. We will prove that, for every subset $S \subset E$, the family of columns $(a_e)_{e \in S}$ is linearly independent in $k^V$ if and only if $S$ contains no cycle. Here a loop is counted as a cycle of length $1$, and two parallel edges joining the same pair of vertices form a cycle of length $2$. [/step] [step:Produce a nonzero column dependence from every cycle] Let $S \subset E$ contain a cycle $C$. If $C$ is a loop edge $e$, then $a_e = 0$, so the one-term relation \begin{align*} 1_k a_e = 0 \end{align*} is a nonzero linear dependence among the columns indexed by $S$. Now suppose $C$ is a cycle of length $m \geq 2$. Choose a cyclic traversal \begin{align*} v_0, e_1, v_1, e_2, \dots, e_m, v_m = v_0 \end{align*} of $C$, where the vertices $v_0,\dots,v_{m-1}$ are distinct and each edge $e_i$ joins $v_{i-1}$ to $v_i$. Define coefficients $\lambda_{e_i} \in k$ by \begin{align*} \lambda_{e_i} = \begin{cases} 1_k, & t(e_i)=v_{i-1}\text{ and }h(e_i)=v_i, -1_k, & t(e_i)=v_i\text{ and }h(e_i)=v_{i-1}. \end{cases} \end{align*} For edges of $S$ not in $C$, set the coefficient equal to $0_k$. We claim that \begin{align*} \sum_{i=1}^{m} \lambda_{e_i} a_{e_i} = 0 \in k^V. \end{align*} At a vertex $v_j$ of the cycle, exactly two cycle edges are incident in the traversal: $e_j$ enters $v_j$ and $e_{j+1}$ leaves $v_j$, with indices taken modulo $m$. The coefficient convention gives contribution $1_k$ from the entering edge and contribution $-1_k$ from the leaving edge, so the total coordinate at $v_j$ is $0_k$. At every vertex outside the cycle, all coordinates of the involved columns are $0_k$. Hence the displayed sum is the zero vector. Each coefficient $\lambda_{e_i}$ is either $1_k$ or $-1_k$, hence is nonzero in the field $k$. Therefore this relation is a nonzero linear dependence among the columns indexed by $S$. Thus every edge set containing a cycle is dependent. [guided] The goal is to show that a graph-theoretic cycle forces a linear dependence among the incidence columns. A loop is the simplest case: by definition its column is $0 \in k^V$, and therefore \begin{align*} 1_k a_e = 0 \end{align*} is already a nonzero dependence. Now consider a cycle with at least two edges. Choose a traversal \begin{align*} v_0, e_1, v_1, e_2, \dots, e_m, v_m = v_0 \end{align*} where $e_i$ joins $v_{i-1}$ to $v_i$. The only issue is that the arbitrary orientation of $e_i$ may agree or disagree with the traversal. We compensate for this by assigning \begin{align*} \lambda_{e_i} = \begin{cases} 1_k, & t(e_i)=v_{i-1}\text{ and }h(e_i)=v_i, -1_k, & t(e_i)=v_i\text{ and }h(e_i)=v_{i-1}. \end{cases} \end{align*} This coefficient makes the contribution of $e_i$ at the vertex it enters equal to $1_k$, and the contribution at the vertex it leaves equal to $-1_k$. Indeed, fix a cycle vertex $v_j$. The edge $e_j$ enters $v_j$ in the traversal, so $\lambda_{e_j}a_{e_j}(v_j)=1_k$. The edge $e_{j+1}$ leaves $v_j$ in the traversal, so $\lambda_{e_{j+1}}a_{e_{j+1}}(v_j)=-1_k$. No other edge of the cycle is incident to $v_j$, because the vertices in the traversal are distinct except for $v_m=v_0$. Hence the $v_j$-coordinate of the sum is \begin{align*} \lambda_{e_j}a_{e_j}(v_j)+\lambda_{e_{j+1}}a_{e_{j+1}}(v_j)=1_k+(-1_k)=0_k. \end{align*} Every vertex outside the cycle receives contribution $0_k$ from every cycle edge. Therefore \begin{align*} \sum_{i=1}^{m} \lambda_{e_i} a_{e_i} = 0 \in k^V. \end{align*} The dependence is nonzero because each $\lambda_{e_i}$ is $1_k$ or $-1_k$, both nonzero in a field. This also covers characteristic $2$: in that case $-1_k=1_k$, and the cancellation still reads $1_k+1_k=0_k$. [/guided] [/step] [step:Use leaf vertices to prove every forest gives independent columns] Let $S \subset E$ contain no cycle. Then $S$ contains no loop, and the spanning subgraph $F = (V,S)$ is a finite forest. We prove that the columns $(a_e)_{e \in S}$ are linearly independent. Define $k^S$ to be the $k$-vector space of functions $S \to k$. Suppose that scalars $(\mu_e)_{e \in S} \in k^S$ satisfy \begin{align*} \sum_{e \in S} \mu_e a_e = 0 \in k^V. \end{align*} We show that $\mu_e = 0_k$ for every $e \in S$. If $S = \varnothing$, there is nothing to prove. Otherwise, choose a connected component $T$ of $F$ containing at least one edge. Since $T$ is a finite tree, it has a leaf vertex $v \in V$, meaning that exactly one edge $e_0 \in S$ is incident to $v$ inside $F$. Evaluating the displayed vector equation at the coordinate $v$ gives \begin{align*} 0_k = \sum_{e \in S} \mu_e a_e(v) = \mu_{e_0} a_{e_0}(v). \end{align*} Because $e_0$ is not a loop, $a_{e_0}(v)$ is either $1_k$ or $-1_k$, hence nonzero. Therefore $\mu_{e_0}=0_k$. Remove $e_0$ from $S$ and repeat the same argument on the smaller forest. Since $S$ is finite, this process terminates after finitely many removals and forces every coefficient $\mu_e$ to be $0_k$. Hence the only linear relation among the columns indexed by $S$ has all coefficients equal to $0_k$, so those columns are linearly independent. [/step] [step:Identify the represented matroid with the cycle matroid] Let $N_k$ be the vector matroid over $k$ represented by the columns $(a_e)_{e \in E}$ of $A_k$; thus a subset $S \subset E$ is independent in $N_k$ exactly when the family $(a_e)_{e \in S}$ is linearly independent in $k^V$. The previous two steps show that, for every $S \subset E$, the set $S$ is independent in $N_k$ exactly when $S$ contains no cycle. By the definition of the cycle matroid $M(G)$, its independent sets are exactly the edge subsets of $G$ that contain no graph-theoretic cycle, with loops counted as cycles of length $1$ and parallel-edge pairs counted as cycles of length $2$. Therefore $N_k$ and $M(G)$ have the same ground set $E$ and the same independent sets, so \begin{align*} N_k = M(G). \end{align*} Since the field $k$ was arbitrary, $M(G)$ is representable over every field. By definition, this means that $M(G)$ is regular. [/step]