When is a matroid a graphical one?

144 Views Asked by At

I'm struggling with the definition of a graphical matroid.

Let $ G = (V, E)$ be an undirected graph. Matroid $M = ( E,I ),$ where $I= \{ F ⊆ E : F$ is acyclic $\}$ ; ie, forests in G. So if $M$ follows this rule than we can state that $M$ is a graphical matroid.

Example:

$M = (E, I) = (\{1,2,3\}, \{\{\emptyset, \{1\}, \{2\}, \{3\}, \{2, 3\}, \{1, 2\}\}$

Bases = $\{\{2,3\}, \{1,2\}\}$ and Circuits = $\{\{1,3\}\}$ also $\{1,2,3\}$ but it's not minimal.

Should I interpret the $I$ as labeled edges between vertices ? edges $ \{1\}, \{2\}, \{3\}$ alone don't make much sense to me.

(wrong) attempt to draw

enter image description here

1

There are 1 best solutions below

4
On BEST ANSWER

The matroid $M$ in the question is graphical, because it arises from the following graph: There are three vertices, which I'll call $a$, $b$, and $c$. There are three edges. Two of them, which I'll call $1$ and $3$, join vertex $a$ to $b$. (So they are what are often called "parallel" edges.) The remaining edge, which I'll call $2$, joins $a$ to $c$. For this graph, the associated graphical matroid has, as its underlying set $E$, the set $\{1,2,3\}$ of edges. Any single edge constitutes an independent (i.e., acyclic) set, because none of the edges are loops (joining a vertex to itself). Of course, the empty set is also independent. The set $\{1,2\}$ is also independent, as the edges $1$ and $2$ make a path $b-a-c$ and that's acyclic. The same goes for $\{2,3\}$. But $\{1,3\}$ and $\{1,2,3\}$ are dependent, because $\{1,3\}$ is a cycle. So the independent sets in this graph are exactly what you listed as $I$.