Number of possible trees in graph theory

[jaus tail]

Homework Statement

Homework Equations

Reduce the matrix to reduced matrix by removing 1 row completely
Number of trees = determinant of [ Ar times Ar^T ]

The Attempt at a Solution

I removed 4th row to get Ar(reduced matrix)
Then I did Ar times Ar (transpose)
And found it's determinant but I got different answer depending on which row I remove.
Do I randomly remove any row?
Sorry for posting too many homework questions. I have an exam coming up in Feb.

 

[StoneTemplePython]

Long story short, this looks like a mechanical recipe being misapplied. I don't understand your incidence matrices. Or to the extent I do understand them, then the shoe doesn't fit.

- - - - - -
If you're looking for understanding, I would strongly suggest reading chapter 21 of Thirty Three Miniatures. A free pre-publication draft is a available here:

http://kam.mff.cuni.cz/~matousek/stml-53-matousek-1.pdf

(note to moderators: see referring page under "books" here: http://kam.mff.cuni.cz/~matousek/ )

another place to look is:

http://math.mit.edu/~levine/18.312/alg-comb-lecture-19.pdf- - - -
Mechanically there are a few problems here. Technical nit: you aren't just counting trees, you're counting spanning trees.

In general, a clean way to do this is to lop off the final row and final column of the graph Laplacian. (Via graph isomorphism arguments it ultimately doesn't matter, but doing the outermost components is easiest.) There's a few ways to proceed. Key question: what does the graph Laplacian look like?

You can draw the actual picture associated with your incidence matrix and make the graph Laplacian by hand.

What you currently, in effect, are saying is that $\mathbf L = \mathbf A \mathbf A^T$. The (un-normalized aka combinatorial) graph Laplacian is supposed to have the ones vector in its nullspace, such that we always have $\mathbf 1^T \mathbf L \mathbf 1 = 0$.

But in your example $\mathbf 1 ^T \mathbf L \mathbf 1 = \big(\mathbf 1^T \mathbf A\big)\big( \mathbf A^T \mathbf 1\big) \gt 0$. I.e. the fact that $\big( \mathbf A^T \mathbf 1\big) \neq \mathbf 0$ is a red flag that something is amiss with your incidence matrix and/or how you're interpreting / applying it.

 

[jaus tail]

In solved examples all incidence matrix had sum of elements in each columns as 0. So I think there must be a typo in the question.
Do you lop off one row and one column?
Book says to remove only one row to get reduced incidence matrix. It doesn't mention removing any column.

 

[StoneTemplePython]

It depends on whether you're working directly with $\mathbf L$ or instead the incidence matrix $\mathbf A$. If $\mathbf L$, then remove outer most row and column. If working directly with a conforming incidence matrix, then if you work through the multiplications, you'll see just removing the bottom row of the incidence matrix is equivalent.

 

[jaus tail]

What is L? The notes only have A as incidence matrix and Ar as reduced incidence matrix and then there are formula of number of graphs and number of twigs/branches.
Is there some formula of L? What does L mean?

 

[StoneTemplePython]

$\mathbf L$ is the 'regular', aka 'combinatorial' aka 'unnormalized' graph Lapalacian. It is generally defined as the degree matrix minus the adjacency matrix. If your graph is undirected/ symmetric, you generally have a relation to incidence matrix $\mathbf A$ in the form of $\mathbf L = \mathbf {AA}^T$ (or $\mathbf A^T \mathbf A$ depnding on how you set it up.)

check out

https://en.wikipedia.org/wiki/Laplacian_matrix

They also fully define it in the links I gave to a pdf from MIT and a pdf called Thirty Three Miniatures.

(note in general $\mathbf A$ tends to refer to an adjacency matrix, not the incidence matrix, but that's a minor convention.)

The graph Laplacian in some sense is the end-game for looking at interesting stuff in graphs. Your incidence matrix is just a pre-cursor. (Nothing wrong with working directly with the precursor though.)