ES214. Discrete Mathematics. L02 Quiz.
ES214. Discrete Mathematics.
L02 Solutions
Let G be a simple, undirected, and connected graph. Consider the graphic matroid discussed in class, i.e, where:
- the universe U is the set of edges of G, i.e, E(G);
- the family \mathcal{F} of independent sets is the collection of all subsets of edges that are acyclic.
A maximal independent set in a matroid is called a basis, and for this example, the maximal independent sets correspond to spanning trees.
A minimal dependent set in a matroid is called a circuit. In this example, what are the circuits?
The circuits of the graphic matroid are the cycles of the graph G.
Let G be a simple, undirected, and connected graph. Consider the following set system:
- the universe U is the set of edges of G, i.e, E(G);
- the family \mathcal{F} of independent sets is the collection of all subsets of edges that are matchings.
Is this a matroid? Why or why not? Justify your answer.
Not a matroid: consider the graph on the vertex set \{a,b,c,d\} with the edges \{ab, cd, ad\}.
There are two matchings in this instance:
- M_1 := \{ab,cd\}
- M_2: \{ad\}
However, although |M_1| > |M_2|, neither of the edges from M_1 can be added to M_2.
Let G be a simple, undirected, and connected graph. Consider the following set system:
- the universe U is the set of vertices of G, i.e, V(G);
- the family \mathcal{F} of independent sets is the collection of all subsets S of that are independent in G, i.e, the subgraph G[S] has no edges.
Is this a matroid? Why or why not? Justify your answer.
Not a matroid: consider the graph on the vertex set \{a,b,c\} with the edges \{ab, ac\}. There are two independent sets: S_1 := \{b,c\} and M_2: \{a\}, but neither of the vertices from S_1 can be added to S_2.
If the independent sets formed a matroid the problem of finding a maximum independent set would not be NP-complete.
— Comment in class