a. The incidence matrix for an undirected graph G D (V, E) is a |V| |E| matrix M such that M e = 1

a. The incidence matrix for an undirected graph G D (V, E) is a |V| × |E| matrix M such that M_νe = 1 if edge e is incident on vertex ν, and M_νe = 0 otherwise. Argue that a set of columns of M is linearly independent over the field of integers modulo 2 if and only if the corresponding set of edges is acyclic.

Then, use the result of Exercise 16.4-2 to provide an alternate proof that (E, I) of part (a) is a matroid.

b. Suppose that we associate a nonnegative weight w(e) with each edge in an undirected graph G = (V, E). Give an efficient algorithm to find an acyclic subset of E of maximum total weight.

c. Let G(V,E) be an arbitrary directed graph, and let (E, I) be defined so that A ∈ I if and only if A does not contain any directed cycles. Give an example of a directed graph G such that the associated system (E, I) is not a matroid. Specify which defining condition for a matroid fails to hold.

d. The incidence matrix for a directed graph G = (V, E) with no self-loops is a |V| × |E| matrix M such that M_νe = −1 if edge e leaves vertex ν, M_νe = 1 if edge e enters vertex ν, and M_νe = 0 otherwise. Argue that if a set of columns of M is linearly independent, then the corresponding set of edges does not contain a directed cycle.

e. Exercise 16.4-2 tells us that the set of linearly independent sets of columns of any matrix M forms a matroid. Explain carefully why the results of parts (d) and (e) are not contradictory. How can there fail to be a perfect correspondence between the notion of a set of edges being acyclic and the notion of the associated set of columns of the incidence matrix being linearly independent?