Courses βΈ± Algorithms

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

#### Lecture Recording

#### In-class Quiz Questions

We continue exploring examples and non-examples of matroids.

- 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?
- Yes
- No

## Reveal answer

Yes

There are no cycles among the highlighted edges.

- 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?
- Empty set.
- All singleton edges; i.e, the size of the family is 7 for the example above.
- All subsets of edges belong to the family; i.e, the size of the family is 128 for the example above
- None of the above

## Reveal answer

Empty set.

There is no edge whose removal keeps connected.

- 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?)* - Also connected.
- May or may not be connected.
- Will not be connected.
- None of the above.

## Reveal answer

Also connected

is a supergraph of which was already connected.

- 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 .
- at least
- at least
- at least

## Reveal answer

at least

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

- 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.
- Yes
- No, it violates the first axiom (empty set membership)
- No, it violates the second axiom (heredity)
- No, it violates the third axiom (exchange axiom)

## Reveal answer

Yes

- Let be an arbitrary undirected graph. Let be the ground set, and let be the family of all subsets of that form a matching. Does this family form a matroid?
*(Hint: Consider a path on four vertices and three edges. Can you find two matchings here that may give you some insights on one of the axioms?)* - Yes
- No, it violates the first axiom (empty set membership)
- No, it violates the second axiom (heredity)
- No, it violates the third axiom (exchange axiom)

## Reveal answer

No, it violates the third axiom (exchange axiom)

Follow the hint.

Β