Question

Let A be incidence matrix of graph G. prove if G has a cycle, then null space of transpose of A is not {0} (there exists non-trivial solution of (A^T)y=0)

Answer 1

The statement is true. Let G be a simple disconnected graph and u,v ∈ V (G). If u and v belong to different components of G, then the edge uv ∈ E( ¯ G). If u and v belong to the same component of G, choose a vertex w in another component of G. (G has at least two components, since it is disconnected.) But then the edges uw and wv belong to E( ¯ G). That is, in all cases there is a u,v-path in ¯ G. then the null space of the transpose A is not zero.

Let G be a graph and let A(G) be its incidence matrix. Now each row in A(G) is a vector over GF(2) in the vector space of graph G. Let the row vectors be denoted by A1, A2, ..., An. Then,
Consider the sum of any m of these row vectors, m ≤ n−1. Since G is connected, A(G) cannot be partitioned in the form A(G) = A(G1) 0 0 A(G2)
such that A(G1) has m rows and A(G2) has n−m rows. Thus there exists no m×m submatrix of A(G) for m ≤ n−1, such that the modulo 2 sum of these m rows is equal to zero. As there are only two elements 0 and 1 in this eld, the additions of all vectors taken m at a time for m = 1, 2,..., n−1 gives all possible linear combinations of n−1 row vectors. Thus no linear combinations of m row vectors of A, for m ≤ n−1, is zero.
Therefore, rank A(G) ≤ n−1.
Combining and , it follows that rank A(G) = n−1.