MA515 Homework #6Due Wednesday, October 131. Exercise 10.11 from my notes.2. Problem (Unique-circuit property), page 53 of the Jon Lee book.3. Exercise (Linear over GF(2) does not imply graphic), page 54 of the Jon Lee b ook.4. Exercise (Nonrepresentable matroids), page 56 of the Jon Lee book.5. Let G be a graph with vertex set V (G) and edge set E(G), and no loops. A walkin G is a sequence of vertices and edges, v0, e1, v1, e2, . . . , vk−1, ek, vksuch that eihasendpoints vi−1and vi, i = 1, . . . , k. Two vertices v and w are in the same componentof G if there is walk from v to w. A graph with exactly one component is said tobe connected. A cycle in G is a walk with at least two edges, no repeated edges, andno repeated vertices except that vk= v0. A graph is acylic or a forest if it does notcontain any cycles. A graph is a tree if it is a connected forest. Orient each edge of Garbitrarily, so that e ach edge has one endpoint designated as its tail and the other asits head. Define the matrix B, with rows indexed by the vertices of G and the columnsindexed by the edges of G, by Bve= −1 if v is the tail of e, 1 if v is the head of e, and0 otherwise. This matrix B is to be regarded as a matrix over the real numbers. Solvethe following problems, noting the useful linear algebra facts that are listed at the endof the assignment. Most of what you need for (c)–(f) can be derived from (a)–(b).(a) Prove that a subset of columns of B is linearly dependent iff the correspondingset of edges of G contains a cycle.(b) Prove that a subset of rows of B is linearly dependent iff the corresponding set ofvertices of G contains all of the vertices of at least one component of G.(c) Prove that G is connected iff dim{y : yTB = OT} = 1 iff rank(B) = |V (G)| − 1.(d) Prove that G is acylic iff dim{x : Bx = O} = 0 iff rank(B) = |E(G)|.(e) Prove that G contains a unique cycle iff dim {x : Bx = O} = 1 iff rank(B) =|E(G)| − 1.(f) Prove that the following statements are equivalent:i. G is a tree.ii. G is connected and |E(G)| = |V (G)| − 1.iii. G is connected, but deleting any edge of G disconnects G into precisely twocomponents.iv. G is acyclic and |E(G)| = |V (G)| − 1.v. G is acyclic, but adding a new edge between any pair of vertices in V (G)creates a unique cycle.Here are some useful facts from linear algebra, for a matrix M with m rows and n columns:• The column rank of M is the maximum size of a linearly independent subset of columns.The row rank of M is the maximum size of a linearly independent subset of rows. Itis a theorem that the column rank of M always equals the row rank of M , so we callthis s imply the rank of M .• The nullspace of M is {x : Mx = O}. The leftnullspace of M is {y : yTM = OT}. It is atheorem that rank(M)+dim(nullspace(M)) = n and rank(M)+dim(leftnullspace(M))