# Graphic matroids - What's wrong with this simple example?

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

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

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

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

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?

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.