You are currently browsing the category archive for the ‘Graph Theory’ category.

This is an elementary (yet important) fact in matrix analysis.


Let M be an n\times n complex Hermitian matrix which means M=M^* where * denote the conjugate transpose operation. Let \lambda_1, \neq \lambda_2 be two different  eigenvalues of M. Let x, y be the two eigenvectors of M corresponding to the two eigenvalues \lambda_1 and \lambda_2, respectively.

Then the following is true:

\boxed{\lambda_1 \neq \lambda_2 \iff \langle x, y \rangle = 0.}

Here \langle a,b\rangle denote the usual inner product of two vectors x,y, i.e.,

\langle x,y \rangle := y^*x.

Read the rest of this entry »

We will show that the eigenvalues of the n\times n Laplacian matrix L of the complete graph K_n are \{0,1\} where  the eigenvalue 0 has (algebraic) multiplicity 1 and the eigenvalue n has multiplicity n-1.

Read the rest of this entry »

In this post, we provide a proof of Kirchhoff’s Matrix Tree theorem [1] which is quite beautiful in our biased opinion. This is a 160-year-old theorem which connects several fundamental concepts of matrix analysis and graph theory (e.g., eigenvalues, determinants, cofactor/minor, Laplacian matrix, incidence matrix, connectedness, graphs, and trees etc.). There are already many expository articles/proof sketches/proofs of this theorem (for example, see [4-6, 8,9]). Here we compile yet-another-expository-article and present arguments in a way which should be accessible to the beginners.


Suppose  L is the Laplacian of a connected simple graph G with n vertices. Then the number of spanning trees in G, denoted by t(G), is the following:

t(G)=\frac{1}{n} \times \{ the product of all non-zero eigenvalues of L\ \}.

Read the rest of this entry »

In this post I will discuss my own understanding of the spectral sparsification paper by Daniel Spielman and Nikhil Srivastava (STOC 2008). I will assume the following:

  1. The reader is a beginner, like me, and have already glanced through the Spielman-Srivastava paper (from now on, the SS paper).
  2. The reader has, like me, a basic understanding of spectral sparsification and associated concepts of matrix analysis. I will assume that she has read and understood the Section 2 (Preliminaries) of the SS paper.
  3. The reader holds a copy of the SS paper while reading my post.

First, I will mention the main theorems (actually, I will mention only what they “roughly” say).

Read the rest of this entry »