1
$\begingroup$

I am trying to understand the definition of graphic Matroids in Cormen's Introduction to algorithms. However, I have trouble understanding it for the simple example shown below. But first Cormen's definition:

According to the book, a graphic matroid $(S_G, I_G)$ is defined in terms of a given undirect graph $G=(V, E)$ as follows:

  • $S_G$ is the set of edges $E$
  • $A \in I_G$ if and only if A is acylic, i.e. the graph $(V, A)$ forms a forest

Next, he provides a short proof and shows that $(S_G, I_G)$ is a matroid.

However, in the following example I have graph that generates a graphic matroid which seems to viloate the properties of a matroid. Consider the graph

enter image description here

This graph is undirected, so it generates a graphic matroid $(S_G, I_G)$, which should have the properties of a matroid.

However, consider the subgraph

enter image description here

with a set of edges $A$ with $|A|=2$ and the subgraph

enter image description here

with a set of edges $B$ with $|B|=3$. $A$ and $B$ are elements of $I_G$ because they are forests. Since $|B|>|A|$, we can use the exchange property of a matroid to add one edge from B to A and obtain

enter image description here

If $(S_G, I_G)$ would form a matroid, this new set of edges would also be part of $I_G$ and hence would have to be a acylic. However, it clearly contains a cycle. Thus $(S_G, I_G)$ should be no matroid.

This would violate the Theorem that all undirected graphs form matroids. What am I missing here?

$\endgroup$

1 Answer 1

3
$\begingroup$

You are moving the wrong edge to $B$. Move the rightmost edge, not the one in the triangle.

The matroid property means that there is some edge $e$ in $B-A$ with $A\cup\{e\}$ independent, not that every edge $e\in B-A$ has $A\cup\{e\}$ independent.

$\endgroup$
1
  • $\begingroup$ Thanks a lot, that is exactly the single word that I misread. $\endgroup$
    – physicsGuy
    Commented Jul 12, 2018 at 9:33

You must log in to answer this question.

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