# 12 Aug, 2021

CoursesAlgorithms
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
Yes
There are no cycles among the highlighted edges.
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 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
Empty set.
There is no edge whose removal keeps connected.
1. 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.
1. 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.
1. 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)