# 12 Aug, 2021

You can also access the quiz on Itempool here if you want to practice, or see the notes below for more context.

### In-class Quiz Questions

📝

We continue exploring examples and non-examples of matroids.

1. Let be a undirected and connected graph. Let be the ground set. A subset is independent if the complementary subgraph of is connected. Consider the example shown in the figure below. Do the highlighted edges form an independent set?
1. Yes
2. No
3.  Yes

There are no cycles among the highlighted edges.

2. Let be a undirected and connected graph. Let be the ground set. A subset is independent if the complementary subgraph of is connected. Consider the example where the graph G is a star, as shown below. What is the family of independent sets?
1. Empty set.
2. All singleton edges; i.e, the size of the family is 7 for the example above.
3. All subsets of edges belong to the family; i.e, the size of the family is 128 for the example above
4. None of the above
5.  Empty set.

There is no edge whose removal keeps connected.

3. Suppose is subset of edges such that is connected. Further, let be a subset of What can you say about ? (Hint: think about in terms of . Is it a subgraph? A supergraph?)
1. Also connected.
2. May or may not be connected.
3. Will not be connected.
4. None of the above.

Also connected

is a supergraph of which was already connected.

4. Suppose is a subset of edges such that is connected. Suppose is a subset of edges such that is connected. Further, suppose . What can we say about the number of edges in ? Pick the strongest claim you can make. Hint: since is connected, it must have at least how many edges? Now put two and two together given that .
1. at least
2. at least
3. at least

at least

A connected graph with exactly one cycle will have at least edges.

5. Let be an undirected and connected graph. Let be the ground set. A subset is independent if the complementary subgraph of is connected. Does this collection of independent sets form a matroid? Hint: for the exchange axiom, consider that a graph with at least n edges has a cycle.
1. Yes
2. No, it violates the first axiom (empty set membership)
3. No, it violates the second axiom (heredity)
4. No, it violates the third axiom (exchange axiom)