The rank of $X$ in $M^*(G).$

60 Views Asked by At

If $X$ is a set of edges in a graph $G,$ how can we know the rank of $X$ in $M^*(G)$ in terms of $G[X].$

Where $M^*(G)$ is the dual of the graphic matroid of $G.$

Some thoughts

We know that for all subsets $X$ of the ground set $E$ of a matroid $M,$ the rank function of $M^*,$ denoted by $r^*$ is given by $$r^* (X) = r(E - X) + |X| - r(M).$$

We also know that the rank in $M(G)$ of a subset $X$ of $E(G)$ is given by $$r(X) = |V(G[X])| - \omega(G[X])$$

Then substituting the second equation in the first one, we will get $$r^* (X) = |V(G[E \setminus X])| - \omega(G[E\setminus X]) + |X| - |V(G[X])| + \omega(G[X]).$$

But then how can we complete? Any hint will be greatly appreciated!

edit:

I am also guessing that my substitution for $r(M)$ at the end of the equation of $r^*(X)$ is wrong, am I correct?

Edit:

$\omega$ is the number of components of a graph $G.$