2 Some basic notions 2.3 Walks, Trails and Paths 2.5 Graphs as metric spaces

2.4 Graphs and matrices : A little peek

We shall now give a brief hint about utility of matrices and linear algebra in answering graph-theoretic questions.

Definition 2.36 (Adjacency matrix.).

Let $G$ be a graph on $n$ vertices. For simplicity, assume $V=[n]$ . The adjacency matrix $A:=A(G):=\left(A(i,j)\right)_{1\leq i,j\leq n}$ of a simple finite graph is defined as follows : $A(i,j)=\mathbf{1}[i\sim j]$ . The definition can be appropriately extended for multi-graphs.

$A$ is a symmetric matrix and hence has real eigenvalues. Define length of a walk/path $P$ as the number of edges in the path $P$ . We denote it by $l(P)$ .

Lemma 2.37.

Let $G$ be a graph on $n$ vertices and $A$ be its adjaceny matrix. Then $A^{l}(i,j)$ is the number of walks of length $l$ from $i$ to $j$ .

Proof.

By definition, $A^{l}(i,j)=\sum_{i_{1},\ldots,i_{l-1}}A(i,i_{1})A(i_{1},i_{2})\ldots A(i_{l-1}% ,j)$ and since $A$ is a $0-1$ valued matrix, we get that $A(i,i_{1})A(i_{1},i_{2})\ldots A(i_{l-1},j)\in\{0,1\}$ . The proof is complete by noting that $A(i,i_{1})A(i_{1},i_{2})\ldots A(i_{l-1},j)=1$ if $i\sim i_{1}\sim i_{2}\ldots i_{l-1}\sim j$ i.e., $ii_{1}\ldots i_{l-1}j$ is a walk of length $l$ . ∎

Exercise(A) 2.38.

Let $\lambda_{1},\ldots,\lambda_{n}$ be the eigenvalues of $A$ . Show that the number of closed walks of length $l$ in $G$ is $\sum_{i=1}^{n}\lambda_{i}^{l}$ . Here, we count the walk $v_{1},\ldots,v_{l-1},v_{1}$ and $v_{2},\ldots,v_{l-1},v_{1},v_{2}$ as distinct walks.

Exercise(A) 2.39.

Count the number of closed walks of length $l$ in the complete graph $K_{n}$ .

The distance between two vertices is defined as $d(u,v)=\inf\{l(P):\mbox{$P$ is a path from $u$ to $v$}\}.$ We set $d(u,u)=0$ and $d(u,v)=\infty$ if there is no path from $u$ to $v$ . One can show that $d$ defines a metric on a connected graph (see Section 2.5).

Lemma 2.40.

Let $G$ be a connected graph on vertex set $[n]$ . If $d(i,j)=m$ , then $I,A,\ldots,A^{m}$ are linearly independent.

Proof.

Assume $i\neq j$ . Since there is no path from $i$ to $j$ of length less than $m$ , $A^{k}(i,j)=0$ for all $k<m$ (show this claim) and $A^{m}(i,j)>0$ . Thus, if $I,A,\ldots,A^{m}$ are linearly dependent with coefficients $c_{0},\ldots,c_{m}$ , then by the above observation and positivity of entries of $A^{k}$ for all $k$ , we have that $c_{m}=0$ i.e., $I,A,\ldots,A^{m-1}$ are linearly dependent. Since $d(i,j)=m$ , there exists $j^{\prime}$ such that $d(i,j^{\prime})=m-1$ (show this claim). Now applying the above argument recursively, we get that $c_{0}=c_{1}=\ldots=c_{m}=0$ . ∎

Define $\operatorname{diam}(G)=\max\{d(u,v):u,v\in V\}$ .

Corollary 2.41.

Let $G$ be a connected graph with $k$ distinct eigenvalues. Then $k>\operatorname{diam}(G)$ .

Proof.

Let $d=\operatorname{diam}(G)$ . Recall that the minimal polynomial of a matrix $A$ is the monic polynomial $Q$ of least degree such that $Q(A)=0$ . By Lemma 2.40, we have that $\deg(Q)>d$ . The proof is complete by observing that the number of distinct eigenvalues of $A$ is $\deg(Q)$ as $A$ is symmetric. ∎

Exercise* 2.42.

How would you define $A$ for multi-graphs or weighted graphs ? Which of the above results hold in such cases ?

2.4 ***Graphs and matrices : A little peek***

Definition 2.36 (Adjacency matrix.).

Lemma 2.37.

Proof.

Exercise(A) 2.38.

Exercise(A) 2.39.

Lemma 2.40.

Proof.

Corollary 2.41.

Proof.

Exercise* 2.42.

2.4 Graphs and matrices : A little peek