1.7.

Isomorphic Graphs
Example:

Consider the following graphs, are they the isomorphic, i.e.

the “same”?

No. The left-hand graph has 5 edges; the right hand graph
has 6 edges.

WUCT121 Graphs 25
Š

Firstly, label the graphs. It “looks” true, so check all the

things we know:

v1 v'1
v5
v' 4 v' 3
v2
v4
v3 v' 2 v' 5

G G′

Number of vertices: both 5.

Number of edges: both 5.
Degrees of corresponding vertices: all degree 2.
Connectedness: Each is fully connected.
Number of connected components: Both 1.
Pairs of connected vertices: All correspond.
Number of loops: 0.
Number of parallel edges: 0.
Everything is equal and so the graphs are isomorphic.

WUCT121 Graphs 26
More formally:

G = {V , E} where V = {v1 , v 2 , v3 , v 4 , v5 } and

E = {( v1 , v 2 ), ( v 2 , v3 ), ( v3 , v4 ), ( v 4 , v5 ), ( v5 , v1 )}
= {e1 , e2 , e3 , e4 , e5 }

G ′ = {V ′, E ′} where V ′ = {v1′ , v 2′ , v3′ , v 4′ , v5′ } and

E ′ = {( v1′ , v 2′ ), ( v 2′ , v3′ ), ( v3′ , v 4′ ), ( v 4′ , v5′ ), ( v5′ , v1′ )}
.
{ ′ ′ ′
= e1 , e2 , e3 , e4 , e5′ ′ }
Construct 2 functions: f : V → V ′ and g : E → E ′

f :V → V ′ g : E → E′

V V′ E E′
v1 v1′ e1 e1′

v2 v 2′ e2 e2′

v3 v3′ e3 e3′

v4 v4′ e4 e4′

v5 v5′ e5 e5′

WUCT121 Graphs 27
1.7.1. Definition

Let G = {V , E} and G ′ = {V ′, E ′} be graphs. G and G ′ are

said to be isomorphic if there exist a pair of functions
f : V → V ′ and g : E → E ′ such that f associates each
element in V with exactly one element in V ′ and vice versa;
g associates each element in E with exactly one element in
E ′ and vice versa, and for each v ∈V , and each e ∈ E , if v
is an endpoint of the edge e, then f ( v ) is an endpoint of the
edge g ( e) .

Notes:

∗ To prove two graphs are isomorphic you must give

a formula (picture) for the functions f and g.

∗ If two graphs are isomorphic, they must have:

- the same number of vertices

- the same number of edges

- the same degrees for corresponding vertices

- the same number of connected components

- the same number of loops

WUCT121 Graphs 28
 - the same number of parallel edges.

∗ Further,

- both graphs are connected or both graphs are not

connected, and

- pairs of connected vertices must have the

corresponding pair of vertices connected.

∗ In general, it is easier to prove two graphs are not

isomorphic by proving that one of the above properties
fails.

WUCT121 Graphs 29
Exercises:

Š Show that the following graphs are isomorphic.

WUCT121 Graphs 30
Š Draw all possible graphs having 2 edges and 2 vertices;
that is, draw all non-isomorphic graphs having 2 edges and
2 vertices.

Since isomorphic graphs are “essentially the same”, we can

use this idea to classify graphs.

WUCT121 Graphs 31
1.8. Regular, Complete and Complete
Bipartite.

1.8.1. Definition: Regular.

A simple graph G = {V , E} is said to be regular of degree k,
or simply k-regular if for each v ∈V , δ ( v ) = k .

That is, if a graph is k-regular, every vertex has degree k.

Exercises:

Š Draw all 0-regular graphs with

1 vertex; 2 vertices; 3 vertices.

1 vertex: 2 vertices: 3 vertices:

Š Draw all 1-regular graphs with

1 vertex; 2 vertices; 3 vertices; 4 vertices.

1 vertex and 3 vertices not possible

WUCT121 Graphs 32
Š Draw all 2-regular graphs with 2 vertices; 3 vertices; 4
vertices.

1.8.2. Definition: Complete.

A simple graph G = {V , E} is said to be complete if each
vertex of G is connected to every other vertex of G.

The complete graph with n vertices is denoted K n .

Notes:

∗ A complete graph is connected

∗ ∀n ∈  , two complete graphs having n vertices are

isomorphic

∗ For complete graphs, once the number of vertices is

known, the number of edges and the endpoints of each edge
are also known

WUCT121 Graphs 33
Example:

Draw K 5

v1
v5
v2

v4 v3

Exercises:

Š Draw K1 , K 2 , K 3 and K 4 . What is the degree of each

vertex in each of the graphs drawn?

WUCT121 Graphs 34
Š Complete the following sentences:

o A complete graph, K n , is an -regular

graph.

o A complete graph, K n , has edges.

[Use Euler’s First Law: ∑δ (v ) = 2n(E ).]
v∈V

WUCT121 Graphs 35
1.8.3. Definition: Bipartite.
A simple graph G = {V , E} is said to be bipartite if there
exists sets U ⊂ V and W ⊂ V , such that;

1. U ∪ W = V and U ∩W = 

2. every edge of G connects a vertex in U with a

vertex in W .

Notes:

∗ A bipartite graph G = {V , E} is one whose vertices

can be separated into two disjoint sets, where every edge
joins a vertex in one set to a vertex in the other

∗ ∀u ∈ U , δ (u ) ≤ n(W ) and ∀w ∈ W , δ ( w) ≤ n(U )

[ n(W ) is the number of elements in W]

WUCT121 Graphs 36
Example:

Consider the following graph G = {V , E}, where

V = {u1 , u 2 , w1 , w2 , w3 } , is it bipartite? Yes

u1 u2

e2 e4
e1 e3

w1 w2 w3

List the sets U and W. U = {u1 , u 2 }; W = {w1 , w2 , w3 }

Exercises:

Š Consider the following graphs, are they bipartite? If so

write down the sets U and W.

o
u1 u2

e1 e2

w1 w2

WUCT121 Graphs 37
 o
u1 w2

w1 u2

Š Draw two bipartite graphs with 5 vertices.

o Where U has 1 element and W has 4 elements.

o Where U has 2 elements and W has 3 elements.

WUCT121 Graphs 38
1.8.4. Definition: Complete Bipartite.
A simple graph G = {V , E}, is said to be complete bipartite
if;

1. G is bipartite and

2. every vertex in U is connected to every vertex in

W.

Notes:

∗ A complete bipartite graph is one whose vertices

can be separated into two disjoint sets where every vertex
in one set is connected to every vertex in the other but no
vertices within either set are connected.

∗ The symbol K n, m is used to denote the complete

bipartite graph having n vertices in one set and m in the

other. [Note that the comma is necessary!]

∗ ∀u ∈ U , δ (u ) = n(W ) and ∀w ∈ W , δ ( w) = n(U )

∗ n( E ) = n × m

WUCT121 Graphs 39
Examples:

Š Draw K 2, 2 Š Draw K 2, 3

K 2, 2 K 2, 3

Exercises:

Š Draw K1, 3

Š Draw K 2, 4

WUCT121 Graphs 40
Š Which of these graphs are bipartite.

WUCT121 Graphs 41
1.9. Eulerian Graphs.
Problem 1:

If you are walking in the park, can you cross each bridge
exactly once?

Does it depend on where you start?

Could you do it with less bridges?

Could you do it with more bridges?

Problem 2:

The Koenigsberg Bridge Problem.

WUCT121 Graphs 42
Can you stroll around, crossing each bridge exactly once
and return to your starting point?

No one can do it.

How do you prove it can't be done?

If you're Leonhard Euler, you make some definitions, make

the problem precise and prove a theorem!

Redraw the problem as a graph:

1.9.1. Definition: Circuit.

Let G = {V , E} be a graph and let v ∈ V . A circuit in G is a
path from v to v in which no edge is repeated.

Note: A circuit is a closed path and in many books is called

a cycle.

WUCT121 Graphs 43
Exercises:

Š Write down the circuits in the following graph, starting

at the given vertices.

o v2 :

o v1 :

o v3 :

o v7 :

1.9.2. Definition: Eulerian Path

Let G = {V , E} be a graph. A path in G is an Eulerian path
if every edge of G is included once and only once in the
path.

WUCT121 Graphs 44
1.9.3. Definition: Eulerian Circuit
Let G = {V , E} be a graph. A circuit in G is an Eulerian
circuit if every edge of G is included exactly once in the
circuit.

1.9.4. Definition: Eulerian Graph

Let G = {V , E} be a graph. G is an Eulerian graph if G has
an Eulerian circuit.

Exercises:

Š Which of these graphs are Eulerian?

K3 K4
v1 v1 v2
v 2 v3 v3 v4

v1
v5
v2

v4 v3 K 2, 3

K5

WUCT121 Graphs 45
Š Can you find an Eulerian path in the following graph
that is not an Eulerian circuit?

e1
v1 v2 e2
e6 e4 v3
v5 v4 e3
e5

Š Is the graph Eulerian?

In the Koenisberg Bridge Problem, we wanted to start and

end at the same vertex. That is, we need to prove that the
graph K is not Eulerian. How?

1.9.5. Theorem: Euler's Theorem.

Let G be a connected graph. G is an Eulerian graph if and
only if the degree of each vertex is even.

WUCT121 Graphs 46
For the Koenisberg Bridge Problem:

δ (C ) = 3 , so the graph is not Eulerian.

Discussion:

Is the “connectedness” condition in Euler's Theorem

necessary?

Consider the graph

Each vertex has even degree but there is no Eulerian

circuit.

WUCT121 Graphs 47
In the Koenisberg Bridge setup, is it possible to cross each
bridge exactly once without necessarily finishing where
you start? That is, is there an Eulerian path in K?

1.9.6. Theorem: Existence of Eulerian Path.

A connected graph has an Eulerian path, which is not a
circuit, if it has exactly two vertices of odd degree.

Example:

δ ( A) = 3 ; δ ( B ) = 5 ; δ (C ) = 3 ; δ ( D) = 3

There are more than 2 vertices of odd degree, therefore, K

does not have an Eulerian path.

WUCT121 Graphs 48