The Representability of Graphic Matroids as Vector Matroids
Matroids are mathematical structures that encapsulate the property of independence. Using a set of defining axioms, matroids can be used to describe concepts across both linear algebra and graph theory. Due to the abstract nature of matroids, it is possible to equivalently describe a matroid of a graph as a matroid of vectors. The main theorem of this paper is that any graphic matroid is representable as a vector matroid over any field . We then use this theorem to propose the total unimodularity of a graph’s incident matrix.
There are many equivalent ways to define a matroid. One such way is by defining it as a pair of sets where is a finite set known as a ground set and is a set of independent subsets of . Additionally, the following properties must be satisfied :
- The set containing nothing is independent: .
- Hereditary: any subset of an independent set is also independent. More formally, for all , if we have , then .
- Augmentation: for all where , there exists such that .
Using this definition, a matroid can be defined relative to different fields of mathematics. For example, by borrowing concepts from graph theory, we define a graphic matroid as representing an undirected graph and an independent set containing the forests of the graph (which will be defined later). Alternatively, a vector matroid can be defined from linear algebra: we can take a matrix and let the independent set represent the sets of columns that are linearly independent.
We say that a matroid is -representable if it is isomorphic to a vector matroid where is a matrix over a field . In this paper, we will prove that every graphic matroid is representable over any field .
Theorem A. All graphic matroids are representable over any field .
Example 1.1. To motivate the main theorem, we start with an example of a graphic matroid and its corresponding vector matroid representation. We denote the graphic matroid of as . Furthermore, let be an arbitrary orientation of . Both and are illustrated below in Figure 1.
Figure 1. A graph of and a corresponding arbitrary orientation .
Based on , we can define a matrix where each column encodes an edge and each row encodes a vertex. The method with which we define this matrix will be defined later in Definition .
It can be observed that any linearly independent subset of columns of correspond to a subset of edges that form a forest of and vice versa. So, each independent set in the matroid of (written ), has a corresponding independent set in . Hence, we say that is isomorphic to .
Matroids were independently discovered by Takeo Nakasawa and Hassler Whitney . In 1935, Whitney introduced the concept of a matroid to describe independence across both linear algebra and graph theory. Whitney discovered that describing graphs and matrices by their hereditary and augmentative properties results in an object that can be interpreted both geometrically and algebraically. Through this, Whitney related the concept of bases, ranks, and circuits to both linear algebra and graph theory, effectively uniting the two mathematical fields .
In 1958, Tutte classified matroids depending on whether they met certain conditions. Namely, Tutte related the condition of a matroid being graphic with a matroid being regular; meaning it is representable over any field .
This paper is structured to build up towards the main Theorem A and explore its applications. Section 2 will introduce the necessary terminology, concepts, and propositions to prove the main theorem. Particularly, the validity of both vector matroids and graphic matroids will be proved. In Section 3, Theorem A will be proved. Section 4 covers a corollary that proposes the matrix representing a graph of a graphic matroid is totally unimodular as a result of Theorem A. Lastly, Section 5 provides questions to motivate additional study of matroids.
This paper assumes the reader is familiar with fundamental linear algebra concepts. Namely, the paper requires prerequisite knowledge of linear independence and matrices as defined in [1, 2.17 and 3.30].
Proposition 2.1. Let be a matrix. If we set the ground set as the set of columns of and as the set of linearly independent column subsets, then is a matroid. A matroid defined in this manner is known as a vector matroid.
Proof. We can prove that is a matroid by showing that it satisfies the three properties outlined in the introduction. Throughout this proof, let be a matrix over an arbitrary field .
Firstly, we know that because the empty set is linearly independent. Hence, the empty set is in . Thus, the first property is satisfied.
Secondly, it can be observed that the hereditary property can be shown to be satisfied by showing that any subset of a linearly independent set is also linearly independent. Let and . We can define and as follows:
Next, let such that we can equate a linear combination of to :
Since we know that , we know that it is linearly independent such that if a linear combination of is equal to , then all scalars must equal . Thus, it must be the case that . Hence, is linearly independent which means . So, if and , then . Therefore, the hereditary property is satisfied.
Thirdly and lastly, we can show that the augmentation property is satisfied using proof by contradiction. Let and be linearly independent subsets of the columns in such that . Furthermore, let . Let be a vector space spanned by over the field . Hence, . Assume that for all , is linearly dependent. Hence, is fully spanned by just , which means . So, we have the inequality
However, we reach a contradiction because , which means the above inequality cannot be true. Thus, for and , there must exist an such that . Hence, the augmentation property holds.
Therefore, since and both the hereditary and augmentation property is satisfied, then is a matroid.
Furthermore, since this paper deals with graphic matroids, it is important to define fundamental graph theory concepts. Some familiarity with graph theory is required to understand how a graphic matroid operates. A graph is a structure consisting of vertices and edges where vertices are connected by edges. A graph may be either directed or undirected depending on whether the edges of the graph have an orientation or not. It should be noted that graphic matroids strictly represent undirected graphs; however, an arbitrary orientation of a graph may be considered to construct its corresponding vector matroid representation. Furthermore, a cycle is a collection of edges that connects some vertex to itself. A tree is an undirected graph where all nodes are connected by a single path, meaning that it is both connected and acyclic.
Definition 2.2. A forest is a disjoint union of trees; each connected component of the forest is a tree.
Example 2.3. Suppose is a connected graph illustrated in Figure 2.
Figure 2. Illustration of connected graph .
Now, we can define : an arbitrary forest of illustrated in Figure 3.
Figure 3. Illustration of forest .
We can observe that is a forest containing trees:
- a tree connecting vertices , , and ,
- a tree connecting vertices and ,
- and a tree consisting of just the vertex.
Proposition 2.4. Let be a graph. Let the ground set be the set of edges of and let be the set of subsets of that form a forest of . Thus, is a matroid. A matroid defined in this manner is known as a graphic matroid.
Proof. Similar to how we proved a vector matroid is indeed a matroid, we can prove that is a matroid by showing it too satisfies the three properties.
Firstly, we know that because a graph consisting of no edges contains no cycles.
Secondly, we can show that the hereditary property is satisfied by . Let and . Additionally, let and denote the number of edges in and respectively. We can consider the following two cases:
- If , then we know that since is a subset of . Since we know that is independent, then it follows that is also independent. Thus, .
- If , it follows that removing any edge from cannot form a cycle. Thus, represents a forest because it does not form any cycles, hence, .
Therefore, satisfies the hereditary property.
Thirdly and lastly, we can show that satisfies the augmentation property using proof by contradiction. Let represent forests of where . Assume there does not exist an edge that connects two disjoint trees in the forest . Then, all the trees in would be subcomponents of the trees in . Since we know that and are both forests, it follows that would have at most edges. So, we reach a contradiction because it was defined earlier that . Thus, adding the edge , which connects two disjoint trees in would still result in a forest. More expressly, . Hence, satisfies the augmentation property.
Therefore, since and both the hereditary and augmentation property is satisfied by , then we can conclude is a matroid.
Definition 2.5. Let be a graph and be an arbitrary orientation of . The incidence matrix of can be defined using the following piecewise definition:
Later, it will be shown that the matroid is isomorphic to the matroid .
Example 2.6. We can use Definition to construct an incidence matrix from an arbitrary graph . To create , we must have some arbitrary orientation of . Let denote an arbitrary orientation of . is illustrated in Figure .
Figure 4. Illustration of : an arbitrary orientation of .
Since has vertices and edges, the resulting incidence matrix will be -by-.
Notably, the column encoding edge is the zero vector because it is a loop: a single edge that connects a vertex directly to itself.
Definition 2.7. A circuit of a matroid is a minimally dependent subset of the ground set. More formally, let be an arbitrary matroid. Let be a circuit of where . Since is a circuit, then for any , it holds that . Also, using the hereditary property of matroids, we know any proper subset of is a member of .
Furthermore, to prove the main theorem, we must rely on the following lemma
Lemma 2.8. Let be a vector space over . Let be a minimally linearly dependent set where all . If a nontrivial (meaning at least one of the scalar coefficients is nonzero) linear combination of vectors in equates to , then all the scalar coefficients must be nonzero.
Proof. Firstly, we can express the linear combination of vectors in with scalars
Since is linearly dependent, we can allow some such that
Suppose . Since is minimally dependent, any subset of is linearly independent. So,
Thus, we find that if some scalar coefficient featured in () is equal to zero, then the rest of the scalar coefficients must be equal to zero. Since is linearly dependent, it must be the case that there is a nontrivial linear combination of . For this to be the case, then all the .
Having defined both vector and graphic matroids and outlined some supporting definitions, we can now prove Theorem . To do so, we must prove that every graphic matroid has a corresponding vector matroid representation over an arbitrary field . The graphic and vector matroids must be isomorphic for them to be equivalent.
Theorem A. All graphic matroids are representable over any field .
Proof. Let be an arbitrary undirected graph and be the matroid of . Let be a matrix defined by the piecewise equation in Definition 2.5 over the field . Let denote the matroid of . Note that to prove that a graphic matroid is representable over any field, it also must be the case that it is representable over the field . Hence, any mention of in the proof should be interpreted as the additive inverse of , which is simply in the case of .
To prove that is isomorphic to , it suffices to prove that there is a bijective mapping taking each independent set in to a corresponding independent set in . Since a subset of a ground set is always either independent or dependent, we can equivalently prove that there is bijection from a dependent set in to a dependent set in . Hence, to prove the main theorem, we shall prove:
- A dependent set in is also dependent in .
- A dependent set in is also dependent in .
Firstly, we can start by proving that a dependent set in is correspondingly dependent in . Let be a dependent set in . Hence, we can consider the following two exhaustive cases:
- contains a loop. The piecewise equation given in Definition only sets a nonzero value if the corresponding edge is a non-loop. So, if were to contain a loop, then one of the corresponding columns in the matrix would be the zero vector. Consequently, any subset containing this column would be linearly dependent, so would be dependent in if it contains a loop.
- does not contain a loop. Since we know is dependent in and there are no loops, then must have at least one cycle.
Let be a cycle.
We can represent as a sequence of edges where where is the ground set of :
Let be the corresponding columns of the matrix where each encodes the edge . While traversing from to , we multiply each by defined as follows:Hence, we end up with a linear combination of :Next, we can justify that the above linear combination equates to . Since form a cycle, then there must be a nontrivial trail connecting some vertex to itself. Thus, for every path going away from a node, there must be a path going back towards the node. Hence, by defining the appropriately, we find that the linear combination equates to such that we have:Hence, since the , then are linearly dependent. Thus, is dependent in . Since and any superset of a linearly dependent set is linearly dependent, then must be dependent in too.
Secondly, we can prove that a dependent set in is correspondingly dependent in . Let be a dependent set in . Let denote a minimally dependent set (a circuit) as declared in Definition . We can define further by considering some subset of individual columns of as such that
If contains a zero vector, it must be the case that for it to be minimally linearly dependent. Some column that is the zero vector simply encodes a loop edge, which means the corresponding set in would also be dependent. Since is dependent in , then would also be dependent in .
Now, we can consider the case when does not contain the zero vector. Since it is linearly minimally dependent, we can use Lemma such that for we have
In other words, we have a linear combination of vectors with all nonzero scalar coefficients equate to . This means for every row of the matrix formed by , there would be at least two nonzero entries. Since each row encodes a single vertex and each row has at least two nonzero entries, then it is equivalent to saying that each vertex has at least two connecting edges. Furthermore, we can observe that for a connected graph with vertices to be acyclic, it can have at most edges. If every vertex (out of vertices) has at least two connecting edges, then there must be at least edges, which means it must be cyclic. Therefore, is dependent in . Consequently, would also be correspondingly dependent in .
In conclusion, we have shown that both a dependent set in is dependent in and a dependent set in is dependent in . Hence, there is a bijection mapping between the dependent sets in and . So, is isomorphic to . Therefore, any graphic matroid can be represented as a vector matroid, so all graphic matroids are representable over any field .
Having proven Theorem A, we know any theorem pertaining to -representable matroids also pertains to graphic matroids. One such theorem is the equivalency between a matroid being -representable and being representable over by a totally unimodular matrix [2, 5.16]. We can show that Theorem A holds by showing that Corollary 4.2 is true for any graphic matroid.
Definition 4.1. ([2, 5.16]) A matrix is called totally unimodular if the determinant of any of its square submatrices is either , , or .
Corollary 4.2. Let be a finite graph and the corresponding graphic matroid. Let be the incident matrix of . Then, must be a totally unimodular matrix.
Proof. To prove Corollary 4.2, we can use a proof by induction approach by showing that every square submatrix has determinant either , , or .
The base case is when the square submatrix is -by-. Let be a -by- square submatrix of . From Definition 2.5, we know that all entries in are either , , or . Hence, we know
Therefore, we know . Thus, the base case holds.
Next, assume that the determinant of a -by- square submatrix is , , or . Then, we shall prove that a -by- square submatrix also has its determinant either , , or . Let be a -by- square submatrix of . Then, fits in the following cases:
- One of the columns in is the zero vector. If one of the columns in is the zero vector, then it cannot be the case that the columns form a basis because it would be linearly dependent. Hence, , which means .
- One of the columns in has a single nonzero entry.
Let the th column be a column of such that it has a single nonzero entry.
We can write the determinant of by conducting cofactor expansion along the th column:
Since there exists only one such that , then only one of the summands of the above sum can be nonzero. Let be the row denoting the only nonzero entry of the th column. Then, the can be expressed as followsSince we know or , and is , , or (because of the inductive hypothesis), thenHence, .
- All columns in have exactly two nonzero entries.
If all columns have exactly two nonzero entries, then each column has a single and a single .
Let denote the corresponding rows of .
Since each column has a single and , we have:
Hence, there exists a linear combination of the rows of such that it equates to and not all scalar coefficients are nonzero. So, is linearly dependent, so they cannot jointly form a basis. Therefore, .
Thus, in every case, . Therefore, by induction, every square submatrix of has a determinant of either , , or . Equivalently, is therefore totally unimodular.
Questions for future study will be outlined in this section.
Question 5.1. How can a vector matroid representation of a graphic matroid be used to computationally solve combinatorial optimization problems?
A combinatorial problem represented as a matroid can be solved using a greedy algorithm . A greedy algorithm is a procedure that finds an optimal solution by choosing a locally optimal solution at each stage. For example, by assigning weights to each element of a matroid’s ground set, a greedy algorithm can be used to find the base (maximally independent set) with minimum weight. This is known as a minimum matroid base problem.
Question 5.2. Although graphic matroids are representable over any field , what are some examples of matroids that are not representable?
 S. Axler. Linear Algebra Done Right. Undergraduate Texts in Mathematics. Springer International Publishing, Cham, 3rd ed. 2015 edition.
 J. Oxley. What is a Matroid? 2014.
 L. Turner, M. Ehrgott, and H. W. Hamacher. On the generality of the greedy algorithm for solving matroid base problems. Discrete Applied Mathematics, 195:114–128, 2015.
 W. T. Tutte. Matroids and graphs. Transactions of the American Mathematical Society, 90(3):527–552, 1959.
 H. Whitney. On the abstract properties of linear dependence. American Journal of Mathematics, 57(3):509, 1935.