MTH229 Chapter 6

December 24, 2024

Definition 1. The adjacency matrix of G is the n × n matrix A with
(
1, if vi vj ∈ E(G)
Aij = .
0, otherwise
1. Show that for any integer k, we have
(Ak )ij = number of walks of length k from vi to vj .

Proof. We prove this by induction. This is true for k = 0 since we can

get from a vertex i to a vertex j in 0 steps if and only if i = j.
Also, it is true for A = 1 by definition. (for n = 2, notice that
Ph
(A2 )ij = k=1 Aik Akj )
Suppose that this is true for k = m(m ∈ N), then for k = m + 1, the
number of walks of length m + 1 from vi to vj is the same as the number
of walks of length m from vi to vk and 1 step from vk to vj . This
number is X
(Am )ik · Akj = Am+1
ij .
k∈V (G)

2. Show that the trace tr(A2 ) is equal to twice the number of edges in G.

Proof. The entry A2ii is the number of closed walks from vi of length
k = 2. A closed walk of length k = 2 counts one edge. Hence,
A2ii = deg(vi ) and therefore
n
X n
X
2
tr(A ) = A2ii = deg(vi ) = 2m,
i=1 i=1

where n is the number of vertices and m is the number of edges in G.

3. Show that the trace tr(A3 ) is equal to six times the number of triangles
in G.

Proof. For each vertex v in a triangle, there are two walks of length
k = 3 that start at v and traverse the triangle. Since each triangle
contains three distinct vertices, each triagle accounts for 6 walks. Thus,
n
X
tr(A3 ) = A3ii = 6t,
i=1

where t is the number of triangles in G.

4. Let G be a graph with adjacency matrix A. Prove that

n=|V (G)|
X
tr(A4 ) = 8q − 2m + 2 deg(vi )2 ,
i=1

where q is the number of 4-cycles in G and m is the number of edges in

G.

1
 Proof. There are three ways to get a closed walk of length k = 4 from vi
to vi .
(1): Closed walk of the form (vi , x, vi , y, vi ), we have deg(vi ) choices for x
and deg(vi ) choices for y.
(2): Closed walk of the form (vi , vj , x, vj , vi ), where vj ∈ N (vi ) and
x ∈ N (vj )\{vi }. The number of walks is
X
(deg(vj ) − 1).
vj ∈N (vi )

(3): Walks along 4-cycles from vi and there are 2 walks for each vi is
contained in, say qi .
Thus, X
A4ii = 2qi + deg2 (vi ) + (deg(vj ) − 1).
vj ∈N (vi )

Therefore,
 
n
X X
tr(A4 ) = 2qi + deg2 (vi ) + (deg(vj ) − 1)
i=1 vj ∈N (vi )
 
n
X X
= 8q + deg2 (vi ) − deg(vi ) + deg(vj )
i=1 vj ∈N (vi )
n
X n
X X
= 8q − 2m + deg2 (vi ) + deg(vj )
i=1 i=1 vj ∈N (vi )
n
X n
X X
= 8q − 2m + deg2 (vi ) + deg(vj )
i=1 j=1 vi ∈N (vj )
| Pn
{z }
j=1 deg2 (vj )

5. For any graph G, it holds that

A(G) + A(G) + I = J(∀1).

Proof. If Aij (G) = 1, then Aij (G) = 0.

6. Prove that G is connected if and only if the matrix (In + A)n−1 has no
0’s.

Proof.
n−2 n−2
(In + A)n−1 = In + Cn−1
1
A + · · · + Cn−1 A + An−1
n−1
X
k
= Cn−1 Ak
k=0

2
 The (u, v)-th entry of Ak is the number of walks of length k from u to v
in G, denoted by Wk (u, v). Thus, the (u, v)-th entry of (In + A)n−1 is
equal to
n−1
X
k
Cn−1 Wk (u, v).
k=0

This is nonzero if and only if Wk (u, v) is nonzero for some

k ∈ {0, 1, · · · , n − 1}.

7.

Lemma 0.0.1. An n × n matrix A is diagonalizable if and only if there

is an invertible matrix P given by
 
P = X1 X2 · · · Xn ,

where the Xk are eigenvectors of A.

Proof. Suppose that P is given as above as an invertible matrix whose

columns are eigenvectors of A. Then P −1 is of the form
 T
W1
W2T 
P −1 =  .  ,
 
 .. 
WnT

where WkT Xj = δkj . Thus,

 T
W1
W2T  
P −1 AP =  .  · AX1 AX2

··· AXn
 
 .. 
WnT
 
 T λ1 0 ··· 0 0
W1 0 λ2 0 ··· 0
W2T    

..


=  .  · λ1 X1
 
λ2 X2 ··· λn Xn = 
0 0 . 0 0.
.
 .   .. 
WnT
 . 
0 0 ··· ··· λn

Conversely, if A is diagonalizable, then let

 
λ1 0 ··· 0 0
0
 λ2 0 ··· 0
   .. 
P = α1 α2 · · · αn D= 0 0 . 0 0,
 .. 
 . 
0 0 ··· ··· λn

we have  
AP = Aα1 · · · Aαn

3
  
λ1 0 ··· 0 0
0
 λ2 0 ··· 0
  ..   
P D = α1 ··· 0
αn  0 . 0 0 = λ1 α1 ··· λn αn .
 .. 
 . 
0 0 ··· ··· λn

Main question: The eigenvectors of Ak are x1 , x2 , · · · , xn with

corresponding eigenvalues λk1 , · · · , λkn .

Proof. Since A is a real symmetric matrix, A is diagonalizable, i.e., there

exist an invertible matrix X and a diagonal matrix D such that
A = XDX −1 . Thus, Ak = XDk X −1 . Thus, Ak X = XDk . By the
Lemma above, we know that the elements on the diagonal of the matrix
Dk are eigenvalues.

Remark: Even if A is not diagonalizable, we can also assert this

property. Notice that if Av = λv, then A2 v = AAv = Aλv = λ2 v.

8. Let G = (V, E) be an arbitrary graph, and let vi , vj be any vertices of

graph G. Let A be the adjacency matrix of graph G. Prove the following
statements:
(a) The number of vi , vj walks of length k in graph G is equal to Akij .
(b) Graph G is bipartite if and only if the eigenvalues of graph G occur
in pairs λ, λ′ such that λ′ = −λ.

Proof. (b) If G is bipartite, then A has the form

 
0 A1
A= .
A2 0
 
v1
If v = is an eigenvector of A with associated eigenvalue λ, then
v2
      
v 0 A1 v1 A1 v 2
λ 1 = = .
v2 A2 0 v2 A2 v 1

Thus,
   
−v1 A1 v 2
A =
v2 −A2 v1
 
λv1
=
−λv2
 
−v1
= −λ .
v2

Conversely, we prove that for each eigenvalue λ ̸= 0, there is another

eigenvalue λ′ = −λ, then G is bipartite.

4
 Notice that G is bipartite if and only if G has no odd cycles. Now,
suppose that A has n eigenvalues λ1 , λ2 , · · · , λn , then Ak has eigenvalues
λk1 , · · · , λkn . From our assumption, we have
n
X
tr(Ak ) = λki = 0.
i=1

If there is an odd cycle of length k, then it must be the case that

(Ak )ii > 0 for some vertex vi , so that tr(Ak ) > 0.

9. If G is a complete graph, then A(G) = J − I − A(G) = J − I, where J

denotes the all-one matrix.
 
0 1 ... 1
1 0 . . . 1
A = . . .
 
 .. .. . . ... 

1 1 ... 0

has eigenvalues n − 1 and 1:

For λ1 = −1:

det(I + A) = det(A + I)
= det(A − (−1)I)
= 0.
 
1
 .. 
For λ2 = n − 1, verify that Av = λ2 v, where v =  . .
1
Since A + I has rank 1, the null space of A + I has dimension n − 1, thus
λ1 = −1 has multiplicty n − 1 and so λ2 = n − 1 has multiplicty 1.
10. A finite graph G is d-regular if and only if its adjacency matrix has the
eigenvalue λ = d with all the coordinates equal to 1 as the eigenvector.

Proof. Since G is d-regular, each row of its adjacency matrix A will have
d 1’s and n − d 0’s. Let
 
a11 a12 . . . a1n
 a21 a22 . . . a2n 
A= . ..  ,
 
.. ..
 .. . . . 
an1 an2 . . . ann

then
ai1 + ai2 + · · · + ain = d.
Define ⃗v be the n × 1 vector  
1
1
 ..  .
 
.
1

5
 We have
A⃗v = d⃗v .
Thus, d is an eigenvalue of A.

11. For a complete bipartite graph Kp,q , the adjacency matrix is of the form
 
0 B
A= .
BT 0

For instance, K3,3 has matrix of the form

 
0 0 0 1 1 1
0 0 0 1 1 1
 
0 0 0 1 1 1
A= 1 1 1 0
.
 0 0
1 1 1 0 0 0
1 1 1 0 0 0

Thus, it is easy to see that the adjacency matrix of a complete bipartite

graph has rank 2 and det A = 0. So, λ1 = 0 is an eigenvalue of G with
multiplicity n − 2. Since
3
X
λi = a11 + · · · + ann = tr(A),
i=1
√ √
λ2 + λ3 = 0. More: λ2 = − pq, λ3 = pq.
12. Let G = (V, E) be an undirected graph with maximum degree d and let
α1 ≥ · · · ≥ αn be the eigenvalues of its adjacency matrix. Then α1 ≤ d.

Proof. Let λ be an eigenvalue of A(G) = (aij ) with corresponding

eigenvector v = (v1 v2 v3 · · · vn ). Rescale v such that |vk | ≤ 1 for all k
and |vi | = 1 for some i. Now,

|λ| = |λvi |
Xn
=| aij vj |
j=1
n
X
≤ |aij ||vj |
j=1
Xn
≤ |aij | ≤ ∆(G).
i=1

More: All the absolute value of eigenvalues are greater than or equal to
δ(G) = minv∈V (G) deg(v).

6
13. The maximum eigenvalue of the adjacency matrix of a regular graph G is
d, the degree of the graph.

Proof. One way to prove it is to show that d is an eigenvalue of its

adjacency matrix together with the fact that all the eigenvalues are less
than or equal to the degree of G. Another way: here.

14. Let G be a k-regular graph. Prove that:

a) If G is bipartite, then −k is an eigenvalue of G’s adjacency matrix.
b) If −k is an eigenvalue of G’s adjacency matrix, then G is bipartite.

Proof. For a), since G is a k-regular graph, k is an eigenvalue of G and

since G is bipartite, −k is an eigenvalue of G.
For b), we need to assume that G is connected, otherwise there are some
counterexamples like a graph with only K4 , K3,3 as its components.
Note that G is bipartite if and only if all the eigenvalues of G occur in
pairs λ′ , λ such that λ′ = −λ. However, we only have one pair k, −k.
TBC

15. Let G a regular graph with n vertices, m edges and eigenvalues

λ1 , λ2 , · · · , λn . Show that
n
X
λi · λj = −m.
1≤i<j≤n

Proof.
n
X
λi = tr(A) = 0.
i=1
n
X
λ2i = tr(A2 ) = 2m.
i=1

Thus,  
n
!2 n
X 1 X X
λi λj = λi − λ2i  = −m.
i<j
2 i=1 i=1

16. Let G be a non-empty graph and let A be an adjacency matrix of G.

Suppose that µ is a spectral radius of G. Show that I − xA is invertible
for any x ∈ R such that |x| < µ1 .

Proof. Suppose that A has n eigenvalues λ1 , · · · , λn . Then I − xA has

eigenvalues 1 − xλ1 , · · · , 1 − xλn . If

det(I − xA) = (1 − xλ1 ) · · · (1 − xλn ) = 0,

then there exists at least one λi such that 1 − xλi = 0. Then prove by
contradiction.