I have to prove that the columns of the incidence Matrix $M$ of a Graph $G$ are always linearly independent if $G$ is a tree. $G$ has $n$ nodes.
I know that $M \in \{ 0, 1 \}^{n \times (n – 1)}$. So I will write $M=(c_1 | … | c_{n-1})$.
I assume that the easiest way to prove that is to assume that the $c_1, …, c_{n-1}$ are linearly dependent and show that then there exists a cycle, so $G$ is not a tree.
So there are $a_1, …, a_{n-1}$ not all $0$, such that $a_1c_1 + … + a_{n-1}c_{n-1} = 0$. For each $c_i$ there exists one specific edge $e_i \in E(G)$, so there is a bijective map, but I don't see how that could help me.
How do I continue from here? Or is the proof easier if I start differently?
Best Answer
We proceed by induction:
Base case: $n=2$ is true (check)
Suppose it is true for a tree on $n$ nodes then let $T$ be a tree on $n+1$ nodes
$$M = (c_1|...|c_{n-1}|c_n)$$ Without loss of generality, we assume column $n$ represents an edge attached to a leaf. (say node $v_{n+1}$ is a leaf). Removing node $v_{n+1}$ (thus edge $e_n)$ gives another tree on $n$ nodes with incidence matrix $$\bar{M} = (c_1|...|c_{n-1})$$ Which by induction has linearly independent columns. Adding back $v_{n+1}$ we get back our original incidence matrix $M$. let $$a_1c_1 + ... +a_{n-1}c_{n-1} + a_{n} c_n =0$$ Case 1: $a_n =0$ then by linear independence of $c_i$ for $i \leq n-1$ we must have $a_i =0$ for $i\leq n-1$
Case 2: $a_n \neq 0$ then $$a_1c_1 + ... +a_{n-1}c_{n-1} =-a_{n} c_n \Longrightarrow b_1c_1 +... b_{n-1}c_{n-1}=c_n$$ where $b_k = -\frac{a_k}{a_n}$. Thus $c_n$ is linear combination of columns of $\bar{M}$. This gives a contradiction
Recall $c_{n}(v_{n+1}) =1$ since it is incident to node $v_{n+1}$. As $\deg v_{n+1} =1$, it is the only edge with this property hence $$c_{k}(v_{n+1})=0 \quad k\leq n-1$$