Math 778S Spectral Graph Theory

Handout #2: Basic graph theory

Graph theory was founded by the great Swiss mathematician Leonhard Euler
(1707-1783) after he solved the Königsberg Bridge problem: Is it possible to
cross seven bridges exactly once?

x
e
1 e
6
e
2
e
w 5
y
e
4
e
7
e z
3

Figure 1: The map of Königsberg Figure 2: The graph associated with

the Königsberg Bridges

Using graph terminology, Euler gave a complete solution for any similar
problem with any number of bridges connecting any number of landmasses! We
will show and prove his result later.

Definition 1 A graph G is a triple consisting of a vertex set V (G), an edge

set E(G), and a relation that associates with each edge two vertices called its
endpoints.

Example 1 For the problem of the Königsberg Bridges, one can define the
graph as follows. Vertices are landmasses while edges are bridges. We have

V (G) = {w, x, y, x}
E(G) = {e1 , e2 , e3 , e4 , e5 , e6 , e7 }
e1 ↔ {w, x}
e2 ↔ {w, x}
e3 ↔ {w, z}
e4 ↔ {w, z}
e5 ↔ {w, y}
e6 ↔ {x, y}
e7 ↔ {y, z}

Definition 2 A loop is an edge whose endpoints are the same. Multiple edges
are edges that have the same pair of endpoints. A simple graph is a graph without
loops or multiple edges.

1
 For a simple graph, an edge e is uniquely represented by its endpoints u and
v. In this case, we write e = uv (or e = vu), and we say u and v are adjacent.
u is a neighbor of v, and vice versa. An edge e is incident
to u (and v).
A simple graph G on n vertices can have at most n2 edges. The simple
n


graph with n vertices and 2 edges is called the complete graph, denoted by
Kn . The simple graph G on n vertices with 0 edge is called the empty graph.
The graph with 0 vertices and 0 edges is called the null graph.

K3 K4 K5 K6

Figure 3: Complete graphs K3 , K4 , K5 , and K6 .

A cycle on n vertices, written Cn , is a graph with vertex set V (G) = [n] =

{1, 2, 3, . . . , n} and edge set E(G) = {12, 23, 34, . . . , (n − 1)n, n1}.

C3 C4 C5 C6

Figure 4: Cycles C3 , C4 , C5 , and C6 .

A path on n vertices, written Pn , is a graph with vertex set V (G) = [n] =

{1, 2, 3, . . . , n} and edge set E(G) = {12, 23, 34, . . . , (n − 1)n}.

Definition 3 The complement Ḡ of a simple graph G is the simple graph with

vertex set V (Ḡ) = V (G) and edge set E(Ḡ) defined by uv ∈ E(Ḡ) if and only
if uv 6∈ E(G). A clique in a graph is a set of pairwise adjacent vertices. An
independent set in a graph is a set of pairwise non-adjacent vertices.

Definition 4 A graph G is bipartite if V (G) is the union of two disjoint inde-

pendent sets called partite sets of G.

Definition 5 A graph is k-partite if V (G) can be expressed as the union of k

independent sets.

Definition 6 The chromatic number of a graph G, written χ(G), is the mini-

mum number k such that G is k-partite.

2
 A subgraph of a graph G is a graph H such that V (H) ⊂ V (G) and E(H) ⊂
E(G). We says G contains H. A induced subgraph of a graph G is a subgraph
H satisfying
E(H) = {uv | u, v ∈ V (H), uv ∈ E(G)}.

Example 2 Let G1 be the simple graph defined by (see Figure 5)

V (G1 ) = {1, 2, 3, 4, 5}
E(G1 ) = {12, 23, 13, 24, 34, 45}.

1 4 5

3
Figure 5: A simple graph G1 .

{1, 2, 3} is a clique. {1, 4} is an independent set. G1 is not a bipartite graph.

The chromatic number is χ(G1 ) = 3.

2 2

1 4 1 4

3 3
Figure 6: A subgraph of G1 . Figure 7: A induced subgraph of G1 .

3
 An isomorphism from a simple graph G to a simple graph H is a bijection
f : V (G) → V (H) satisfying

uv ∈ E(G) iff f (u)f (v) ∈ E(H).

We say G is isomorphic to H, denoted G ∼

= H.
The isomorphism relation is an equivalence relation. I.e., it is
1. reflexive: A ∼
= A.
2. symmetric: if A ∼
= B, then B ∼
= A.
3. transitive: if A ∼
= B and B ∼
= C, then A ∼
= C.
An isomorphism class of graphs is an equivalence class of graphs under the
isomorphism relation. It is also known as an“unlabeled graph”.

Definition 7 The adjacency matrix of a graph G, written A(G), is the n-by-n

matrix in which entry aij is the number of edges with endpoints {vi , vj } in G.
Here V (G) = v1 , v2 , . . . , vn is the vertex set of G.

For a simple graph G, we have


1 if vi vj is an edge
A(G) =
0 otherwise

A(G) is a symmetric 0-1 matrix with 0s on the diagonal. For a vertex v of the
graph G, the degree dv is the number of edges which are incident to v. If v = vi ,
then dvi is the i-th row/column sum of A(G).

Example 3 For graph G1 (Figure 5), the adjacency matrix is given by

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

Definition 8 A walk (on a graph G) is a list v0 , e1 , v1 , e1 , . . . , ek , vk , satisfying

ei = vi−1 vi is an edge for all i = 1, 2, . . . , k. k is called the length of the walk.
A u, v-walk is a walk with v0 = u and vk = v.
A trail is a walk with no repeated edge.
A path is a walk with no repeated vertices.
A closed walk is a walk with the same endpoints, i.e., v0 = vk .
A cycle is a closed walk with no repeated vertices except for the endpoints.

Lemma 1 Every u, v-walk contains a u, v-path.

4
Proof: We prove it by induction on the length k of the walk.
When k = 1, a u, v-walk is a u, v-path.
We assume that every u, v-walk with length at most k contains a u, v-path.
Now let us consider a u, v-walk u = v0 , e1 , v1 , e1 , . . . , ek+1 , vk+1 = v of length
k + 1. If the walk has no repeated vertices, it is a u, v-path by definition.
Otherwise, say vi = vj for 0 ≤ i < j ≤ k + 1. By deleting all vertices and edges
between vi and vj , we get a new walk: v0 , . . . , vi = vj , . . . , vk+1 . This walk has
length at most k. By the inductive hypothesis, it contains a u, v-path. .

Definition 9 A graph G is connected if it has a u, v-path for any u, v ∈ V (G).

For any u, v, we define a connected relation u ∼ v over V (G) if there is a u, v-

path in G. The connected relation is an equivalence relation. The equivalence
classes for this relation are called connected components of G.
A component is trivial if it contains only one vertex. A trivial component is
also called an isolated vertex.

Lemma 2 Every closed odd walk contains an odd cycle.

Proof: We prove it by induction on the length k of the closed walk.

When k = 1, the walk of length 1 is a loop. Thus, it is an odd cycle.
We assume that every odd walk with length at most k = 2r−1 contains a u, v-
path. Now let us consider a closed walk u = v0 , e1 , v1 , e1 , . . . , e2r+1 , v2r+1 = v
of length 2r + 1. If the walk has no repeated vertices, it is an odd cycle by
definition. Otherwise, say vi = vj for 0 ≤ i < j ≤ 2r + 1. The walk can be split
into two closed walks:
v0 , . . . , vi = vj , . . . , vk+1
vi , . . . , ei+1 , . . . , vj .
One of them must have odd length of at most 2r−1. By the inductive hypothesis,
it contains an odd cycle.
The proof is finished. .

Theorem 1 (König 1936) A graph is bipartite if and only if it has no odd

cycle.

Proof: It is sufficient to prove this for any connected graph.

Necessity: Let G be bipartite graph. Every walk of G alternates between the
two sets of a bipartition. The lengths of any closed walks are even. Therefore,
it has no odd cycle.
Sufficiency: Let G be a graph with no odd cycle. We will construct a
bipartition as follows. Choose any vertex u. We define a partition V (G) = X ∪Y
as follows.

X = {v ∈ V (G)| there is a u, v-path of odd length}.

Y = {v ∈ V (G)| there is a u, v-path of even length}.

5
Since G is connected, we have X ∪ Y = V (G). We will show X ∩ Y = ∅.
Otherwise, let u ∈ X ∩ Y . There are two u, v-paths. One path has even length
while the other one has odd length. Put them together. We have an odd closed
walk. By lemma, G has an odd cycle. Contradiction. Therefore, V (G) = X ∪ Y
is a partition.
Next, we will show there are no edges with both ends in X or Y . Otherwise,
suppose that vw is such an edge. The u, v-path, the edge vw, and the w, u-path
together form an odd closed walk. By previous lemma, G contains an odd cycle.
Contradiction.
Hence, G is a bipartite graph. 
A complete bipartite graph Ks,t has a vertex set partition V = X ∪ Y with
|X| = s and |Y | = t and an edge set E(G) = xy | x ∈ X, y ∈ Y .

Theorem 2 Let λ1 ≥ λ2 ≥ · · · λn be the eigenvalues of the adjacency matrix of

a simple graph G. The the following statements are equivalent.
1. G is a bipartite graph.
2. For all 1 ≤ i ≤ n, λn+1−i = −λi .

Proof: Suppose G is a bipartite graph. Then there exists a vertex set partition
V = X ∪ Y . Reorder vertices so that the vertices in X are before the vertices
in Y . The adjacency matrix A has the following shape:
 
0 B
A= .
B′ 0
 
β
Let α = be an eigenvector corresponding to an eigenvalue λ. Since
γ
Aα = λα, we have

Bγ = λβ
B′β = λα.
 
β
Let α̃ = Then we have
−γ
  
0 B β
Aα̃ =
B′0 −γ
 
−Bγ
=
B′β
 
−λβ
=
λγ
= −λα̃.

This shows −λ is also an eigenvalue of A. The eigenvalues are symmetric about

0.

6
 Suppose λi = −λn+1−i for all i. We have
n
X
tr(A2k+1 ) = λ2k+1
i = 0.
i=1

The number of odd closed walks is 0. G has no odd cycle. Thus, G is bipartite
by Konig’s theorem.