How can I tell if this independence system forms a matroid?

169 Views Asked by At

Let $(V,E)$ be a graph and consider a system $f$ of subsets of $V$ with $U\in f \mbox{ and } \forall u,v\in U$ we have $(u,v)\notin E$. This, $(V,f)$ is trivially an independence system, but how can I further decide whether it is a matroid?

Thank you for any help.

1

There are 1 best solutions below

5
On BEST ANSWER

Consider the graph with vertices $u$, $v$, and $w$ and edges $(u,v)$ and $(v,w)$:

*---*---*
u   v   w

Let $f=\left\{\{v\},\{u,w\}\right\}$. Does $f$ have the augmentation property (independent set exchange property)?