0
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ I am a bit confused. Why do you mention the similarity with rank in linear algebra for the condition? There is certainly some similarity, but the condition you mention is just false. Imagine for instance $I_1$ to be an edge, and $I_3$ to be three edges not having a triangle. We will have $|I_2|>|I_1|$, but because of the cardinalities of $I_1$ and $I_2$ it would be impossible to find $e\in I_2\setminus I_1$ such that $I_1\cup \{e\}=I_2$. Perhaps you want something different? $\endgroup$
    – Darío G
    Commented May 14, 2018 at 13:19
  • $\begingroup$ I am so sorry; I completely messed up the condition. I fixed it now. $\endgroup$
    – W. G.
    Commented May 14, 2018 at 13:24
  • $\begingroup$ It should be that there exists an $e\in I_2-I_1: I_1\cup \lbrace e \rbrace$ is acyclic. $\endgroup$
    – W. G.
    Commented May 14, 2018 at 13:26
  • $\begingroup$ Acording to the definition of matroid it seems that you are trying to proof that given a graph $G=(V,E)$ there is a matroid on $X=E(G)$ were the independent sets are precisely those sets of edges that do not contain cycles. Is that correct? $\endgroup$
    – Darío G
    Commented May 14, 2018 at 13:34
  • $\begingroup$ Yes that is exactly correct $\endgroup$
    – W. G.
    Commented May 14, 2018 at 13:35

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ I really appreciate this answer as it is extremely thorough. I am just a little hung up on the last bullet as to why there are least $k$ connected components for $G_2$? For instance, if $T_1\cap V(G_2)$ was the empty set, then $G_2$ could have less components than $k$. Why can't that happen? $\endgroup$
    – W. G.
    Commented May 14, 2018 at 19:17
  • $\begingroup$ Actually, you have noticed a gap. As it is written now it does not explain what could happen if, for instance, one of the intersections $T_i\cap V(G_2)$ is empty. I will try to fix my answer. $\endgroup$
    – Darío G
    Commented May 14, 2018 at 21:48
  • $\begingroup$ @W.G. Is the end of the proof better now? $\endgroup$
    – Darío G
    Commented May 14, 2018 at 22:09
  • $\begingroup$ I would have accepted this answer multiple times to give you more credit if I could lol. Honestly, I would not have been able to get through this proof without your help. It took me awhile to get through it, because it is so dense. I'm adding this to my list of favorite proofs! Thank you so much!! $\endgroup$
    – W. G.
    Commented May 15, 2018 at 16:16

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .