GRAPH THEORY LECTURE NOTES 11

1.8. Adjacency and incident matrix. For a simple graph with vertex set U = {u1 , · · · , un },
the adjacency matrix is a square n → n matrix A such that its element Aij is one when there
is an edge from vertex ui to vertex uj , and zero when there is no edge.

E
A B

D C
G

A B C D E
 
A 0 1 1 1 1
B 1 0 1 0 0
AG = C 
1 1 0 1 1

D 1 0 1 0 0
E 1 0 1 0 0

In general, for a graph (not necessarily simple) with vertex set U = {u1 , · · · , un }, the adja-
cency matrix is a square n → n matrix A such that its element Aij for i ↑= j is the number
of edges from vertex ui to vertex uj , and zero when there is no edge. Aii is two times the
number of loops based at ui . Clearly, adjacency matrix is symmetric.
The incidence matrix of a simple graph G with n vertices and m edges is a n → m matrix
BG , where n and m are the numbers of vertices and edges respectively, such that
'
1 if vertex vi is incident with edge ej ,
(BG )ij =
0 otherwise.
For example, the incidence matrix of the graph shown on the right is a matrix consisting of
4 rows (corresponding to the four vertices, 1–4) and 4 columns (corresponding to the four
edges, e1 , e2 , e3 , e4 ):

The degree matrix DG os n → n diagonal matrix with (i, i) entry given by degree of i-th
vertex vi .
Exercise: BG BG
T
= A G + DG .

Definition 1.14. For a simple graph G, the Laplacian matrix of G is defined to be LG =

DG ↓ AG .
• The sum the rows of the Laplacian matrix (or the columns, since it’s symmetric), is
always zero.
• Laplacian is a singular matrix
• Null space LG is one dimensional
12 ARUN MAITI

• LG is positive semi-definite matrix, consequently, eigenvalues of LG are non-negative.

Theorem 1.15 (Matrix tree theorem/Kircho! Theorem). For a given connected graph G
with n labeled vertices, let ω1 , ω2 , · · · , ωn be the non-zero eigenvalues of its Laplacian matrix.
Then the number of spanning trees of G is
1
t(G) = ω1 ω2 · · · ωn→1 .
n
Proof. Beyond the scope of this course. ↭

1.9. Isomorphism of graphs. Two graphs G = (V, E) and G↑ = (V ↑ , E ↑ ) are said to be

isomoprhic if there exist a bijective function (called isomorphism) f : V ↔ V ↑ such that
f (e) ↗ E ↑ for every edge e ↗ E.
Example: The following two graphs are isomorphic. It is easy to verify that following bijection
f : V ↔ V given by 1 ↔ A, 2 ↔ C, 3 ↔ B, 4 ↔ D, 5 ↔ E defines an isomorphism.

4
5 3 D E
1 2

A B

u6 u 7 v6 v7 v9

u1 u 2 u 3 u4 u 5 v1 v2 v3 v4 v5
u8 u9 u10 v8 v10

Consider the above two graph. An isomorphism must map a vertex of degree d of the
first graph to a vertex of degree d in the second graph. Therefore, the only vertex with
degree 3, u4 must be mapped to the only vertex of degree 3, v3 . An isomorphism must also
map adjacent vertices to adjacent vertices. Subsequently, u5 (adjacent to u4 ) must map to a
degree 2 vertex adjacent to v3 . But both the vertices adjacent to v3 (v2 and v4 ) have degree 4.
Hence, an isomorphism is impossible. Hence, there doesn’t exist any isomorphism between
the two graph.

Theorem 1.16. Two graphs G and H are isomorphic if and only if there is a permutation
matrix P such that AG = P AH P →1

Proof. Exercise. ↭
 GRAPH THEORY LECTURE NOTES 13

1.10. Bipartite Graph. A bipartite graph (or bigraph) is a graph whose vertices can be
divided into two disjoint and independent sets U and V , that is, every edge connects a vertex
in U to one in V . Vertex sets U and V are usually called the parts of the graph.

A complete bipartite graph is a bipartite graph where every vertex of the first set is
connected to every vertex of the second set. It is denoted by Km,n where m and n denote
the number of vertices in the first and second set respectively.
1.11. Practice problems set 1. 1. Can there exist a graph on 13 vertices and 31 edges,
with three vertices of degree 1, and seven vertices of degree 4? Explain.

2. Given the following degree sequences either construct a graph with such a degree se-
quence, or explain why this would be impossible.
(a) 1,1,1,1,1,1
(b) 5,4,3,2,1
(c) 6,6,4,2,2,2,2,1

3. What is the maximum number of vertices on a graph that has 35 edges and every vertex
has degree ↘ 3?

4. Suppose all vertices in a graph, G, have odd degree, k. Prove that k divides |E(G)|.

5. Given the following two graphs, write an explicit isomorphism between them.

6. Draw all non-isomorphic graphs with n vertices for n = 3 and 4.

7. Can a graph have K3 subgraph and be bipartite? Explain.

14 ARUN MAITI

8. Let G be the following graph:

a) Is the following a subgraph of G?

(b) Draw an induced subgraph of G with exactly 3 edges.