Graph Theory - Lecture 2 (of 2)

Graph Theory

Click here for a movable graph

Graph Theory

a e1
e2 c
b e4
d e3 e5
e6 e e8
e7
G f g

1/25
Graph Theory

a e1
e2 c
b e4
d e3 e5
e6 e e8
e7
G f g

Degree Sequence
deg(a)=

1/25
Graph Theory

a e1
e2 c
b e4
d e3 e5
e6 e e8
e7
G f g

Degree Sequence
deg(a)=1,

1/25
Graph Theory

a e1
e2 c
b e4
d e3 e5
e6 e e8
e7
G f g

Degree Sequence
deg(a)=1, deg(b)=

1/25
Graph Theory

a e1
e2 c
b e4
d e3 e5
e6 e e8
e7
G f g

Degree Sequence
deg(a)=1, deg(b)=4,

1/25
Graph Theory

a e1
e2 c
b e4
d e3 e5
e6 e e8
e7
G f g

Degree Sequence
deg(a)=1, deg(b)=4, deg(c)=

1/25
Graph Theory

a e1
e2 c
b e4
d e3 e5
e6 e e8
e7
G f g

Degree Sequence
deg(a)=1, deg(b)=4, deg(c)=3,

1/25
Graph Theory

a e1
e2 c
b e4
d e3 e5
e6 e e8
e7
G f g

Degree Sequence
deg(a)=1, deg(b)=4, deg(c)=3, deg(d)=

1/25
Graph Theory

a e1
e2 c
b e4
d e3 e5
e6 e e8
e7
G f g

Degree Sequence
deg(a)=1, deg(b)=4, deg(c)=3, deg(d)=2,

1/25
Graph Theory

a e1
e2 c
b e4
d e3 e5
e6 e e8
e7
G f g

Degree Sequence
deg(a)=1, deg(b)=4, deg(c)=3, deg(d)=2, deg(e)=

1/25
Graph Theory

a e1
e2 c
b e4
d e3 e5
e6 e e8
e7
G f g

Degree Sequence
deg(a)=1, deg(b)=4, deg(c)=3, deg(d)=2, deg(e)=3,

1/25
Graph Theory

a e1
e2 c
b e4
d e3 e5
e6 e e8
e7
G f g

Degree Sequence
deg(a)=1, deg(b)=4, deg(c)=3, deg(d)=2, deg(e)=3, deg(f)=

1/25
Graph Theory

a e1
e2 c
b e4
d e3 e5
e6 e e8
e7
G f g

Degree Sequence
deg(a)=1, deg(b)=4, deg(c)=3, deg(d)=2, deg(e)=3, deg(f)=2

1/25
Graph Theory

a e1
e2 c
b e4
d e3 e5
e6 e e8
e7
G f g

Degree Sequence
deg(a)=1, deg(b)=4, deg(c)=3, deg(d)=2, deg(e)=3, deg(f)=2
deg(g)=

1/25
Graph Theory

a e1
e2 c
b e4
d e3 e5
e6 e e8
e7
G f g

Degree Sequence
deg(a)=1, deg(b)=4, deg(c)=3, deg(d)=2, deg(e)=3, deg(f)=2
deg(g)=1.

1/25
Graph Theory

a e1
e2 c
b e4
d e3 e5
e6 e e8
e7
G f g

Degree Sequence
deg(a)=1, deg(b)=4, deg(c)=3, deg(d)=2, deg(e)=3, deg(f)=2
deg(g)=1.
Degree sequence is:

1/25
Graph Theory

a e1
e2 c
b e4
d e3 e5
e6 e e8
e7
G f g

Degree Sequence
deg(a)=1, deg(b)=4, deg(c)=3, deg(d)=2, deg(e)=3, deg(f)=2
deg(g)=1.
Degree sequence is: 1, 1, 2, 2, 3, 3, 4.

1/25
Graph Theory - Bipartite Graph

Bipartite Graph
A bipartite graph Km,n (for m, n ≥ 1) is a simple graph with m + n
vertices. The vertex set partitions into sets X and Y of cardinalities m and
n. And edges are only of the form xy , where x ∈ X , y ∈ Y :

V (Km,n ) = {x1 , x2 , · · · , xm } ∪ {y1 , y2 , · · · , yn }

E (Km,n ) ⊆ {xi yj : xi ∈ X , yj ∈ Y }
2/25
Bipartite Graph, 2-Coloring and No Odd-length Cycle
Theorem
The following are equivalent:
1 G is bipartite.
2 G admits a proper 2-vertex-colouring; that is, the vertices of G can
be coloured with 2 colours (say, red and blue) so that the endpoints
of each edge receive distinct colours.
3 G has no subgraph that is a cycle of odd length.

3/25
Bipartite Graph, 2-Coloring and No Odd-length Cycle
Theorem
The following are equivalent:
1 G is bipartite.
2 G admits a proper 2-vertex-colouring; that is, the vertices of G can
be coloured with 2 colours (say, red and blue) so that the endpoints
of each edge receive distinct colours.
3 G has no subgraph that is a cycle of odd length.

5 6

1 2

3 4

8 7
G
Bipartite Graph, 2-Coloring and No Odd-length Cycle
Theorem
The following are equivalent:
1 G is bipartite.
2 G admits a proper 2-vertex-colouring; that is, the vertices of G can
be coloured with 2 colours (say, red and blue) so that the endpoints
of each edge receive distinct colours.
3 G has no subgraph that is a cycle of odd length.

5 6

1 2

3 4

8 7
G

3/25
Bipartite Coloring

4/25
Bipartite Coloring

4/25
Bipartite Coloring

4/25
Bipartite Coloring

4/25
Matrix Representation of Graphs
Graph Theory - Incident Matrix Representation

Incident Matrix Representation

Let G be a graph with V (G ) = {u1 , u2 , · · · , un },
E (G ) = {e1 , e2 , · · · , em },and incidence function fG . We define:
the incidence matrix of G : an n × m matrix M = [mij ] such that

2, if fG (ej ) = {vj }

mij = 1, if fG (ej ) = {ui , uk } for some k 6= i (1)

0 otherwise.

5/25
Graph Theory - Adjacency Matrix Representation

Adjacency Matrix Representation

Let G be a graph with V (G ) = {u1 , u2 , · · · , un },
E (G ) = {e1 , e2 , · · · , em },and incidence function fG . We define:
the adjacency matrix of G : an n × n matrix A = [aij ] such that

aij = |{ek : fG (ek ) = {ui , uj }}|

= number of edges with end points ui and uj .
6/25
Graph Theory - Adjacency Matrix Representation

7/25
Graph Isomorphism

Graph Isomorphism Problem is one of the most interesting problems in

computer science.

a g 5 6

b h 1 2
c i 3 4

d j 8 7
G H

Click here for an animated example

Graph Isomorphism

Graph Isomorphism Problem is one of the most interesting problems in

computer science.

a g 5 6

b h 1 2
c i 3 4

d j 8 7
G H

Click here for an animated example

Graph Isomorphism

Graph Isomorphism Problem is one of the most interesting problems in

computer science.

An Isomorphism
between G and H
a g 5 6 f (a) = 5 f (b) = 2

b h 1 2 f (c) = 3 f (d) = 7

c i 3 4 f (g ) = 1 f (h) = 6

d j 8 7 f (i) = 8 f (j) = 4
G H

8/25
Graph Isomorphism

Graph Isomorphism Problem is one of the most interesting problems in

computer science.

An Isomorphism
between G and H
a g 5 6 f (a) = 5 f (b) = 2

b h 1 2 f (c) = 3 f (d) = 7

c i 3 4 f (g ) = 1 f (h) = 6

d j 8 7 f (i) = 8 f (j) = 4
G H

Click here for an animated example

8/25
Graph Isomorphism
Are these two graph isomorphic?

Definition (Graph Isomorphism)

Let G and H be simple graphs. An isomorphism from G to H is a
bijection ϕ : V (G ) → V (H) such that

u ∼G v ⇔ ϕ(u) ∼H ϕ(v )
for all u, v ∈ V (G ). Graphs G and H are called isomorphic (denoted
G∼ = H) if there exists an isomorphism from G to H.
9/25
Graph Isomorphism

Definition (Graph Invariant)

A graph invariant is a graph property or parameter that is preserved under
isomorphisms; that is, isomorphic graphs must agree on this property or
parameter. Many graph properties are invariants; for example:
Number of vertices
Number of edges
Degree Sequence (all the degrees of the vertices of the graph in
sorted order)
Being bipartite
Containing specific subgraph etc.

10/25
Graph Isomorphism

Observation
To prove that graphs G and H are isomorphic, we must find an
isomorphism from G to H.
To prove that graphs G and H are not isomorphic, it suffices to find
an invariant in which G and H differ.

11/25
Graph Isomorphism -Example 1

Are these two graph isomorphic?

Solution:

12/25
Graph Isomorphism -Example 1

Are these two graph isomorphic?

Solution:
No. They have the same degree sequence. But these two graphs are not
isomorphic. H has a subgraph isomorphic to C3 , while G does not (it is, in
fact, bipartite and isomorphic to K3,3 ).

12/25
Graph Isomorphism -Example 2
Are these two graph isomorphic?

Solution:

13/25
Graph Isomorphism -Example 2
Are these two graph isomorphic?

Solution:
Yes, these two graphs are isomorphic. An isomorphism ϕ : (G ) → V (H) is
given by

ϕ(1) = a ϕ(2) = d
ϕ(3) = b ϕ(4) = e
ϕ(5) = c ϕ(6) = f
13/25
Graph Isomorphism -Example 3

Are these two graph isomorphic?

Solution:

14/25
Graph Isomorphism -Example 3

Are these two graph isomorphic?

Solution:
No, these two graphs are not isomorphic. They have the same degree
sequence, however, graph H contains no pair of adjacent vertices of degree
3, while G does.

14/25
Walks, Trails, Paths, Cycle
Walks, Trails, Paths, Cycles
Definition
Walk Let G = (V , E ) be a graph with the incidence function fG . Let
x, y ∈ V and k ∈ N. An (x, y )-walk of length k in G is an alternating
sequence of vertices and edges.

15/25
Walks, Trails, Paths, Cycles
Definition
Walk Let G = (V , E ) be a graph with the incidence function fG . Let
x, y ∈ V and k ∈ N. An (x, y )-walk of length k in G is an alternating
sequence of vertices and edges.

A (v1 , v3 )-walk of length 4

W = v1 e2 v2 e6 v4 e8 v3 e7 v3
15/25
Walks, Trails, Paths, Cycles
Definition
A walk W = v0 e1 v1 e2 v2 · · · vk1 ek vk is called
closed if v0 = vk , and open otherwise;
a trail if its edges are pairwise distinct;
a path if its vertices are pairwise distinct; and
a cycle if v0 = vk while its internal vertices v1 , · · · , vk are pairwise
distinct.

16/25
Walks, Trails, Paths, Cycles
Definition
A walk W = v0 e1 v1 e2 v2 · · · vk1 ek vk is called
closed if v0 = vk , and open otherwise;
a trail if its edges are pairwise distinct;
a path if its vertices are pairwise distinct; and
a cycle if v0 = vk while its internal vertices v1 , · · · , vk are pairwise
distinct.

16/25
Walks, Trails, Paths, Cycles
Definition
A walk W = v0 e1 v1 e2 v2 · · · vk1 ek vk is called
closed if v0 = vk , and open otherwise;
a trail if its edges are pairwise distinct;
a path if its vertices are pairwise distinct; and
a cycle if v0 = vk while its internal vertices v1 , · · · , vk are pairwise
distinct.

W = 1a2h6n5f 1a2b3

16/25
Walks, Trails, Paths, Cycles
Definition
A walk W = v0 e1 v1 e2 v2 · · · vk1 ek vk is called
closed if v0 = vk , and open otherwise;
a trail if its edges are pairwise distinct;
a path if its vertices are pairwise distinct; and
a cycle if v0 = vk while its internal vertices v1 , · · · , vk are pairwise
distinct.

W = 1a2h6n5f 1a2b3
is a (1,3)-walk of length 6 that is not a trail.

16/25
Walks, Trails, Paths, Cycles
Definition
A walk W = v0 e1 v1 e2 v2 · · · vk1 ek vk is called
closed if v0 = vk , and open otherwise;
a trail if its edges are pairwise distinct;
a path if its vertices are pairwise distinct; and
a cycle if v0 = vk while its internal vertices v1 , · · · , vk are pairwise
distinct.

W = 1a2h6n5f 1a2b3
is a (1,3)-walk of length 6 that is not a trail.

W = 1e4d4c3

16/25
Walks, Trails, Paths, Cycles
Definition
A walk W = v0 e1 v1 e2 v2 · · · vk1 ek vk is called
closed if v0 = vk , and open otherwise;
a trail if its edges are pairwise distinct;
a path if its vertices are pairwise distinct; and
a cycle if v0 = vk while its internal vertices v1 , · · · , vk are pairwise
distinct.

W = 1a2h6n5f 1a2b3
is a (1,3)-walk of length 6 that is not a trail.

W = 1e4d4c3
is a (1,3)-trail of length 3 that is not a path.

16/25
Walks, Trails, Paths, Cycles
Definition
A walk W = v0 e1 v1 e2 v2 · · · vk1 ek vk is called
closed if v0 = vk , and open otherwise;
a trail if its edges are pairwise distinct;
a path if its vertices are pairwise distinct; and
a cycle if v0 = vk while its internal vertices v1 , · · · , vk are pairwise
distinct.

W = 1a2h6n5f 1a2b3
is a (1,3)-walk of length 6 that is not a trail.

W = 1e4d4c3
is a (1,3)-trail of length 3 that is not a path.

W = 1f 5m8k3
16/25
Walks, Trails, Paths, Cycles
Definition
A walk W = v0 e1 v1 e2 v2 · · · vk1 ek vk is called
closed if v0 = vk , and open otherwise;
a trail if its edges are pairwise distinct;
a path if its vertices are pairwise distinct; and
a cycle if v0 = vk while its internal vertices v1 , · · · , vk are pairwise
distinct.

W = 1a2h6n5f 1a2b3
is a (1,3)-walk of length 6 that is not a trail.

W = 1e4d4c3
is a (1,3)-trail of length 3 that is not a path.

W = 1f 5m8k3
is a (1,3)-path of length 3. 16/25
Walks, Trails, Paths, Cycles
Definition
A walk W = v0 e1 v1 e2 v2 · · · vk1 ek vk is called
closed if v0 = vk , and open otherwise;
a trail if its edges are pairwise distinct;
a path if its vertices are pairwise distinct; and
a cycle if v0 = vk while its internal vertices v1 , · · · , vk are pairwise
distinct.

W = 2b3j7i2h6o7i2

17/25
Walks, Trails, Paths, Cycles
Definition
A walk W = v0 e1 v1 e2 v2 · · · vk1 ek vk is called
closed if v0 = vk , and open otherwise;
a trail if its edges are pairwise distinct;
a path if its vertices are pairwise distinct; and
a cycle if v0 = vk while its internal vertices v1 , · · · , vk are pairwise
distinct.

W = 2b3j7i2h6o7i2 is a closed walk of length

6 that contains vertex 2 and is not a trail:.

17/25
Walks, Trails, Paths, Cycles
Definition
A walk W = v0 e1 v1 e2 v2 · · · vk1 ek vk is called
closed if v0 = vk , and open otherwise;
a trail if its edges are pairwise distinct;
a path if its vertices are pairwise distinct; and
a cycle if v0 = vk while its internal vertices v1 , · · · , vk are pairwise
distinct.

W = 2b3j7i2h6o7i2 is a closed walk of length

6 that contains vertex 2 and is not a trail:.

W = 4d4l8k3c4

17/25
Walks, Trails, Paths, Cycles
Definition
A walk W = v0 e1 v1 e2 v2 · · · vk1 ek vk is called
closed if v0 = vk , and open otherwise;
a trail if its edges are pairwise distinct;
a path if its vertices are pairwise distinct; and
a cycle if v0 = vk while its internal vertices v1 , · · · , vk are pairwise
distinct.

W = 2b3j7i2h6o7i2 is a closed walk of length

6 that contains vertex 2 and is not a trail:.

W = 4d4l8k3c4 is a closed trail of length

4 that contains vertex 4 and is not a cycle.

17/25
Walks, Trails, Paths, Cycles
Definition
A walk W = v0 e1 v1 e2 v2 · · · vk1 ek vk is called
closed if v0 = vk , and open otherwise;
a trail if its edges are pairwise distinct;
a path if its vertices are pairwise distinct; and
a cycle if v0 = vk while its internal vertices v1 , · · · , vk are pairwise
distinct.

W = 2b3j7i2h6o7i2 is a closed walk of length

6 that contains vertex 2 and is not a trail:.

W = 4d4l8k3c4 is a closed trail of length

4 that contains vertex 4 and is not a cycle.

W = 2b3j7o6h2
17/25
Walks, Trails, Paths, Cycles
Definition
A walk W = v0 e1 v1 e2 v2 · · · vk1 ek vk is called
closed if v0 = vk , and open otherwise;
a trail if its edges are pairwise distinct;
a path if its vertices are pairwise distinct; and
a cycle if v0 = vk while its internal vertices v1 , · · · , vk are pairwise
distinct.

W = 2b3j7i2h6o7i2 is a closed walk of length

6 that contains vertex 2 and is not a trail:.

W = 4d4l8k3c4 is a closed trail of length

4 that contains vertex 4 and is not a cycle.

W = 2b3j7o6h2 is a cycle of length 4

containing vertex 2. 17/25
Trees and Forests
Trees and Forests
Warm up: Connected Graph

Connected Graph
A graph G = (V , E ) is called connected if for any x, y ∈ V there exists an
(x, y )-path (or equivalently, (x, y )-walk) in G . A graph that is not
connected is called disconnected.

18/25
Trees

Tree and Forest

A graph without cycles is called acyclic or a forest. A tree is a connected
acyclic graph ,that is, a connected forest.

19/25
Trees
Theorem 1
Let G be a graph. Then G is a tree if and only if for any two vertices
u, v ∈ V (G ), there exists a unique (u, v )-path in G .

Theorem 2 and 3
Every tree with at least 2 vertices has at least 2 vertices of degree 1
(called leaves).
Any tree with n vertices has exactly n − 1 edges.
20/25
Rooted Trees

Rooted Tree
A tree with a vertex designated as the root is called a rooted tree.

21/25
Rooted Trees
Similar terminologies for rooted trees?

22/25
Rooted Trees
Terminology for rooted trees:
Let T = (V , E ) be a rooted tree with root r and u, v ∈ V .
If u lies on the unique (v , r )-path, then u is called anancestor of v ,
and v is called a descendant to u.
If u lies on the unique (v , r )-path and uv has an edge, then u is called
the parent of v , and v is called a child of u.
If u and v have the same parent, then they are called siblings.
If vertex u has a child, then it is called an internal vertex; if it has
no children, thenit is called a leaf.

23/25
Rooted m-ary Trees

A Rooted m-ary Tree:

an m-ary tree if every internal vertex has at most m children; and
a full m-ary tree if every internal vertex has exactly m children.
A Binary is a 2-ary tree.
A Ternary is a 3-ary tree.

24/25
Thank you for your attention!!

25/25