Proof of Graphic Matroids (Using Rank in Context of Graph Theory)

Question

The rank of a graphic matroid given by an edge set $X$ can be denoted as $r(X)=n-c$ where $n$ is the number of vertices in the subgraph of edges $X$ and $c$ is the number of connected components of $X$. It is clear to me that $r(X)$ also can be defined as the number of edges given by the minimum spanning forest of $X$, i.e. of course edge weight $1$.

I am wanting to prove the following condition for graphic matroids (e.g. $I_1$ and $I_2$ are acyclic edge sets) in a way that relies upon this concept of rank.

Condition: If $I_1, I_2\in \mathcal{I}$ and $|I_2|>|I_1|$, then $\exists e\in I_2-I_1: I_1\cup \lbrace e \rbrace\in \mathcal{I}$.

I feel the concept of rank in graphic matroids is very similar to the concept of rank in linear algebra to prove this result, but I could be wrong. I have not seen a clear cut way of proving how graphic matroids can be proved without going into detail as to how graphic matroids are representable as vector Matroids. I feel like there is a way of proving graphic matroids with this concept of rank which avoids representability in this way. Does anyone have any insight on how to do this? I would be very gracious to learn.

Answer 1

Following the definition of a matroid, we are trying to show that given a graph $G=(V,E)$ there is a matroid on $X=E(G)$ were the collection of independent sets $\mathcal{I}$ is precisely the collection of sets of edges that do not contain cycles.

Clearly, $\emptyset\in\mathcal{I}$ (if there are no edges, there will be no cycles) and $A\subseteq A'\in \mathcal{I}$ implies $A\in\mathcal{I}$ (if $A'$ does not contain cycles, neither does $A$ because it has less edges).

We are left with the condition the OP mentioned:

If $I_1,I_2\in \mathcal{I}$ and $|I_2|>|I_1|$, then there is $e\in I_2$ such that $I_1\cup \{e\}\in \mathcal{I}$.

To show this we can use some common facts about trees (i.e., connected graphs without cycles).

---

Proposition 1: Let $T=(V,E)$ be a tree (a connected graph with no cycles). Then:

1. $|V(T)|=|E(T)|+1$.
2. Any new edge in $T$ will produce a cycle.

Sketch of proof: The proof of (1) goes by induction on $|V(T)|$. In the inductive step choose a leaf $x$ (a vertex of degree 1) and notice that $T'=T\setminus \{x\}$ is also a tree, with one vertex and one edge less than $T$.

To prove (2), note that for any vertices $x,y\in T$ there is already a path $P$ connecting them. Thus, if $e=\{x,y\}$ is a new edge, $P\cup \{e\}$ will induce a cycle. $\Box$

Proposition 2: If $G$ is a graph containing no cycles with $k$ connected components, then $|E(G)|=|V(G)|-k$

Proof: Let $T_1,\ldots,T_k$ be the connected components of $G$. Then each $T_i$ is a tree, and by Proposition 1 we have $|E(T_i)|=|V(T_i)|-1$ for each $i=1,2,\ldots,k$. Therefore,

$$\begin{align*} |E(G)|&=|E(T_1)|+\cdots + |E(T_k)|\\ &=(|V(T_1)|-1)+\cdots + (|V(T_k)|-1)\\ &=(|V(T_1)|+|V(T_2)|+\cdots + |V(T_k)|)-k\\ &=|V(G)|-k. \hspace{1cm} \Box \end{align*}$$

---

Now, suppose that $I_1,I_2$ are acyclic subsets of edges of a graph $G=(V,E)$ with $|I_2|>|I_1|$, and let us consider the graphs $G_1,G_2$ whose edge sets are respectively $E(G_1)=I_1$ and $E(G_2)=I_2$.

Note that for an edge $e=\{x,y\}$ to complete a cycle with $I_1$, it is necessary that the vertices $x,y$ of $e$ are contained in $V(G_1)$ and there is a $G_1$ connecting $x$ with $y$. So, we have the following three cases:

• If there is a vertex $x\in V(G_2)\setminus V(G_1)$, then $x$ is contained in an edge $e\in I_2$ and $I_1\cup \{e\}$ will be acyclic.
• Otherwise, we would have $V(G_2)\subseteq V(G_1)$. Let $T_1,\ldots,T_k$ be the connected components of $G_1$. If there is an edge $e\in I_2$ connecting elements $x\in T_i,y\in T_j$ from different connected components, then $I_1\cup \{e\}$ is also acyclic because there was no path in $G_1$ connecting $x$ and $y$.
• Finally, if none of the above is true, then $G_2$ is an acyclic graph with vertex set contained in $V(T_1)\cup\cdots \cup V(T_k)$ and whose edges connect elements of each $T_i$ only with elements of the same $T_i$.

In the last case, let us denote by $E_{G_1}(T_i)$ the edges of $G_1$ connecting points in $T_i$, and by $E_{G_2}(T_i)$ the edges of $G_2$ connecting points in $T_i$. (i.e., $E_{G_1}(T_i)$ denotes the edges in $I_1$ whose endpoints belong to $T_i$, while $E_{G_2}(T_i)$ denotes the edges in $I_2$ whose endpoints belong to $T_i$).

Since $|I_1|=|E_{G_1}(T_1)|+\cdots + |E_{G_1}(T_k)|<|E_{G_2}(T_1)|+\cdots+|E_{G_2}(T_k)|=|I_2|$, there is some $i\leq k$ such that $|E_{G_1}(T_i)|<|E_{G_2}(T_i)|$. Note that $E_{G_2}(T_i)\subseteq I_2$, so it induces an acyclic graph with vertex set $T_i\cap V(G_2)$, say with $s\geq 1$ connected components. By Proposition 2 we have

$$|E_{G_2}(T_i)|=|T_i\cap V(G_2)|-s\leq |V(T_i)|-s\leq |V(T_1)|-1=|E_{G_1}(T_i)|,$$ obtaining a contradiction.