Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Is the following is a matroid

  1. Jun 24, 2006 #1
    I would like to know if the following is a matroid:
    Matroid: a matroid M on a ground set E is a pair (S, l), where l is a collection of subsets of S (called the independent sets) with the following properties:
    1. The empty set is independent.
    2. Every subset of an independent set is independent; this is sometimes called the hereditary property.
    3. If A and B are two independent sets and A has more elements than B, then there exists an element in A which is not in B and when added to B still gives an independent set; this property is called the exchange property.

    1. Let G=(V,E) be an undirected graph. Let the set S=E and the independent sets corresponding to acyclic subgraphs with at most two edges is a subset.
  2. jcsd
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Can you help with the solution or looking for help too?
Draft saved Draft deleted

Similar Discussions: Is the following is a matroid
  1. Following inequality (Replies: 12)