Question

Suppose that a spanning tree consists of m nodes, does this mean that there will be m columns in the corresponding incidence matrix? Why or why not?

Answer 1

Incidence matrix is that matrix which represents the graph such that with the help of that matrix we can draw a graph. This matrix can be denoted as [A_c]. As in every matrix, there are also rows and columns in incidence matrix [AC].
The rows of the matrix [A_c] represent the number of nodes and the column of the matrix [A_c] represent the number of branches(edges) in the given graph. If there are ‘n’ number of rows in a given incidence matrix, that means in a graph there are ‘n’ number of nodes. Similarly, if there are ‘m’ number of columns in that given incidence matrix, that means in that graph there are ‘m’ number of branches.

Since a spanning tree with 'm' nodes has exactly 'm-1' edges, so there will be 'm-1' columns in its incidence matrix...