# 12 Aug, 2021

Courses βΈ± Algorithms
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)