Consider the arc incidence matrix E of a graph. This matrix has a row for each node and a column for each arc. The component corresponding to the ith row and a given arc is a 1 if the arc is outgoing from i, is a -1 if the arc is incoming to i, and is a 0 otherwise. Show that E is totally unimodular (cf. the discussion in Section 5.5). Hint: We must show that the determinant of each square sub matrix of E is 0, 1, or -1. Complete the details of the following argument, which uses induction on the dimension of the sub matrix. The sub matrices of dimension 1 of E are the scalar components of E, which are 0, 1, or -1. Suppose that the determinant of each square sub matrix of dimension n ≥ 1 is 0, 1, or -1. Consider a square sub matrix of dimension n + 1. If this matrix has a column with all components 0, the matrix is singular, and its determinant is 0. If the matrix has a column with a single nonzero component (a 1 or a -1), by expanding its determinant along that component and using the induction hypothesis, we see that the determinant is 0, 1, or -1. Finally, if each column of the matrix has two components (a 1 and a -1), the sum of its rows is 0, so the matrix is singular, and its determinant is 0.