Discrete Mathematics

(CSC 1204)

Connectivity

1
 Paths

• A path is a sequence of edges that begins at a

vertex of a graph and travels from vertex to
vertex along edges of the graph.

2
 Paths
• Definition1: Let n be a nonnegative integer and G an
undirected graph. A path of length n from u to v in G is a
sequence of n edges e1, e2 , …., en of G such that
e1 is associated with {x0, x1}, e2 is associated with {x1, x2 }, and
so on, with en associated with {xn-1, xn }, where x0=u and xn=v.
• The path is a circuit if it begins and ends at the same vertex,
that is, if u = v, and has length greater than zero.
• The path or circuit is said to pass through the vertices x1, x2, …,
xn-1 or traverses the edges e1, e2 , …., en .
• A path/circuit is simple if it does not contain the same edge
more than once.
3
Example 1 (p.622)

 In the simple graph shown in Figure, a , d, c, f, e is a simple path

of length 4, because {a , d}, {d, c } , {c, f}, and { f, e} are all edges.
 However, d, e, c, a is not a path, because {e, c} is not an edge.
 Note that b, c, f, e, b is a circuit of length 4 because {b, c}, {c, f},
{f, e}, and {e, b} are edges, and this path begins and ends at b.
 The path a, b, e, d, a, b, which is of length 5, is not simple
because it contains the edge {a, b} twice.

4
 Paths in Directed Graph

• Same as in undirected graphs, but the path must go

in the direction of the arrows.

5
 Connectedness in Undirected Graphs

• An undirected graph is called connected if there is a

path between every pair of distinct vertices of the
graph

6
Example 5 (p.624)

Figure 2: The Graphs G 1 and G2

 The graph G l in Figure 2 is connected, because for every pair

of distinct vertices there is a path between them.
 However, the graph G 2 in Figure 2 is not connected. For
instance, there is no path in G2 between vertices a and d.

7
 Connectivity
• Question: Which of the following graphs are connected?

1 2

3
4

8
 Connectivity
Answer: First and second are disconnected. Last is connected.

1 2

3
4

9
 Connected Components
• A connected component of a graph G is a connected
subgraph of G that is not proper subgraph of another
connected subgraph of G.
• A connected component of a graph G is a maximal
connected subgraph of G.
– A graph G that is not connected has two or more
connected components that are disjoint and have
G as their union.

10
 Connected Components
• Definition: A connected component in a graph G is a set of
vertices such that all vertices in the set are connected to
each other and every possible connected vertex is included.
• Question : What are the connected components of the
following graph?

1
6 2

7
8
5 3
4
11
 Connected Components
• Answer: The components are {1,3,5}, {2,4,6}, {7}
and {8} as one can see visually by pulling
components apart:

1
6 2

8 7
5 3
4

12
 Connectedness in Directed Graphs
• A directed graph is strongly connected if there is a path from
a to b and from b to a whenever a and b are vertices in the
graph.
– For a directed graph to be strongly connected there must
be a sequence of directed edges from any vertex in the
graph to any other vertex
• A directed graph is weakly connected if there is a path
between every two vertices in the underlying undirected
graph.
• Note: Any strongly connected directed graph is also weakly
connected, but the opposite is not true.

13
EXAMPLE: Are the directed graphs G and H shown in Figure
strongly connected? Are they weakly connected?

Weakly Strongly
H is strongly connected because
Connected Connected there is a path between any two
vertices in this directed graph.
Hence, H is also weakly connected.

The graph G is not strongly

connected. There is no directed
path from a vertex to other vertex
in this graph.

G H

14
 Example 9(p.626)
• Graph G is strongly connected (hence G is also weakly connected).
Graph H is not strongly connected, however H is weakly connected.

a b a b

c c

e d e d

Graph G Graph H
15
 Paths and Isomorphism
• There are several ways that paths & circuits can help
determine whether two graphs are isomorphic.
– For example, the existence of a simple circuit of a
particular length is a useful invariant that can be used to
show that two graphs are not isomorphic.
• A useful isomorphic invariant for simple graphs is the
existence of a simple circuit of length k, where k is a
positive integer greater than 2.

16
 Graph Isomorphism – Example
Prove that the graph K is isomorphic to graph R .

K R

1. First label the vertices:

2 2
1 3 1 3

5 4 5 4

17
Graph Isomorphism –Example
2. Next, set f (1) = 1 and try to walk around clockwise on the
star.

2 2
1 3 1 3

5 4 5 4

18
Graph Isomorphism – Example
3. Next, set f (1) = 1 and try to walk around clockwise on the
star. The next vertex seen is 3, not 2 so set f (2) = 3.

2 2
1 3 1 3
5 4
5 4

19
 Graph Isomorphism – Example

4. Next, set f (1) = 1 and try to walk around clockwise on the

star. The next vertex seen is 3, not 2 so set f (2) = 3. Next
vertex is 5, so set f (3) = 5.

2 2
1 3 1 3
5 4

5 4

20
 Graph Isomorphism – Example

5. Next, set f (1) = 1 and try to walk around clockwise on the

star. The next vertex seen is 3, not 2, so set f (2) = 3. Next
vertex is 5, so set f (3) = 5. In this fashion we get f (4) = 2

2 2
1 3 1 3
5
4 5 4

21
 Graph Isomorphism – Example
6. Next, set f (1) = 1 and try to walk around clockwise on the
star. The next vertex seen is 3, not 2 so set f (2) = 3. Next
vertex is 5 so set f (3) = 5. In this fashion we get f (4) = 2, f
(5) = 4.

2 2
1 3 1 3

5 4 5 4

22
 Graph Isomorphism – Example
7. Next, set f (1) = 1 and try to walk around clockwise on the star.
The next vertex seen is 3, not 2 so set f (2) = 3. Next vertex is 5
so set f (3) = 5. In this fashion we get f (4) = 2, f (5) = 4. If we
would continue, we would get back to f (1) =1 so this process is
well defined and f is a morphism.

2 2
1 3 1 3

5 4
5 4

23
 Graph Isomorphism – Example
• Next, set f (1) = 1 and try to walk around clockwise on the
star. The next vertex seen is 3, not 2 so set f (2) = 3. Next
vertex is 5 so set f (3) = 5. In this fashion we get f (4) = 2,
f (5) = 4. If we would continue, we would get back to
f (1) =1 so this process is well defined and f is a morphism.
Finally since f is bijective, f is an isomorphism.
• Therefore the graph K is isomorphic to graph R.

2 2
1 3 1 3

5 4
5 4

24
Example12(p.627): Determine whether the graphs G and H
shown in Figure 6 are isomorphic.

Figure 6
25
 Solution
 Both G and H have six vertices and eight edges.
 Each has four vertices of degree three, and two vertices
of degree two.
—all agree for the two graphs G and H
 However, H has a simple circuit of length three, namely,
v1, v2, v6, v1 , whereas G has no simple circuit of length
three, as can be determined by inspection (all simple
circuits in G have length at least four).
 Because the existence of a simple circuit of length three
is an isomorphic invariant, G and H are not isomorphic.

26
Example 13(p.628) : Determine whether the graphs G and H
shown in Figure are isomorphic.

27
 Solution:
 Both G and H have five vertices and six edges.
 Each has two vertices of degree three, and three vertices
of degree two.
 Both have a simple circuit of length three, a simple circuit
of length four, and a simple circuit of length five.
 Because all these isomorphic invariants agree here, so
G and H may be isomorphic.
 …..continued to next slide

28
 Finding of possible isomorphism:
 ………. we will follow paths that go through all vertices so that the
corresponding vertices in the two graphs have the same degree.

 For example, the paths u1, u4,u3, u2, u5 in G and v3, v2, v1, v5, v4 in H both
go through every vertex in the graph; start at a vertex of degree three; go
through vertices of degrees two, three, and two, respectively; and end at a
vertex of degree two.
 By following these paths through the graphs, we can define the mapping f
with
 f (u1) = v3
 f (u2) = v5
 f (u3) = v1
 f (u4) = v2
 f (u5) = v4
 It shows that f is an isomorphism, so G and H are isomorphic.
29
 9.5 Euler and Hamilton Path

• Euler Paths & Circuits

• Hamilton Paths & Circuits

30
 Euler Paths & Circuits

• Euler path: An Euler path in G is a simple path

containing every edge of G.

• Euler circuit: An Euler circuit in a graph G is a

simple circuit containing every edge of G.

31
 Euler Paths & Circuits
• EXAMPLE 1 (p.633): Which of the undirected graphs in Figure below have an Euler
circuit? Of those that do not, which have an Euler path?

 The graph G1 has an Euler circuit, for example, a, e, c, d, e, b, a.

 Neither of the graphs G2 or G3 has an Euler circuit.
 However, G3 has an Euler path, namely, a, c, d, e, b, d, a, b. G2 does
not have an Euler path.
32
 Euler Paths & Circuits
• Theorem 1: A connected multigraph with at least
two vertices has an Euler circuit iff each of its
vertices has even degree.

• Theorem 2: A connected multigraph has an Euler

path (but not an Euler circuit) iff it has exactly two
vertices of odd degree.

33
 Euler Circuit/Path: Example
• EXAMPLE 2 (p.634): Which of the directed graphs in Figure 4 have an Euler circuit?
Of those that do not, which have an Euler path?

• The graph H2 has an Euler circuit, for example,

a, g, c, b, g, e, d, f, a.
• Neither H1nor H3 has an Euler circuit
• H3 has an Euler path, namely, c, a, b, c, d, b,
but H1 does not have Euler path 34
 Determining Euler Circuit/Path: Example
• Example 4(p.637):Which graphs shown in Figure 7 have an
Euler path?

35
 Determining Euler Circuit/Path: Example
 Solution:
• G1 contains exactly two vertices of odd degree, namely, b and
d. Hence, it has an Euler path that must have b and d as its
endpoints.
– One such Euler path is d, a, b, c, d, b.
• Similarly,G2 has exactly two vertices of odd degree, namely, b
and d. So it has an Euler path that must have b and d as
endpoints.
– One such Euler path is b, a, g, f, e, d, c, g, b, c, f, d.
• G3 has no Euler path, because it has six vertices of odd
degree.

36
 Hamilton Paths and Circuits
• Hamilton path: A simple path in a graph that passes
through every vertex exactly once is called a
Hamilton path.
– A Hamilton path does not necessarily pass
through all the edges of the graph
• Hamilton circuit: A simple circuit in a graph G that
passes through every vertex exactly once is called a
Hamilton circuit.

37
 Hamilton Paths and Circuits
EXAMPLE 5(p.639): Which of the simple graphs in Figure 10 have a
Hamilton circuit or, if not, a Hamilton path?

Figure 10 : Three Simple Graphs

38
 Hamilton Paths and Circuits
Solution:
• G1 has a Hamilton circuit: a, b, c, d, e, a.
• There is no Hamilton circuit in G2 (this can be seen by
noting that any circuit containing every vertex must
contain the edge {a, b} twice),
but G2 does have a Hamilton path, namely, a, b, c, d.
• G3 has neither a Hamilton circuit nor a Hamilton
path, because any path containing all vertices must
contain one of the edges {a, b},{e, f }, and {c, d} more
than once.
39
 Hamilton Paths and Circuits
EXAMPLE 6 (p.640): Show that neither graph displayed in Figure 11 has a
Hamilton circuit.

Figure 11
40
 Hamilton Paths and Circuits
• Solution:
• There is no Hamilton circuit in G because G has a
vertex of degree one, namely, e.
• Now consider H. Because the degrees of the vertices
a, b, d, and e are all two, every edge incident with
these vertices must be part of any Hamilton circuit. It
is now easy to see that no Hamilton circuit can exist
in H, for any Hamilton circuit would have to contain
four edges incident with c, which is impossible.

41
 Hamilton Paths and Circuits
• Theorem 3(DIRAC’S THEOREM): If G is a simple
graph with n vertices with n>=3 such that the degree
of every vertex in G is at least n/2, then G has a
Hamilton circuit.
• Theorem 4(ORE’S THEOREM): if G is a simple graph
with n vertices with n>=3 such that
deg(u) + deg(v) >= n for every pair of non-adjacent
vertices u and v in G, then G has a Hamilton circuit.

42
 Hamilton Paths and Circuits
• Both Ore’s Theorem and Dirac’s Theorem
provide sufficient conditions for a connected
simple graph to have a Hamilton circuit.
However, these theorems do not provide
necessary conditions for the existence of a
Hamilton circuit.
– For example, the graph C5 has a Hamilton circuit
but does not satisfy the hypotheses of either Ore’s
Theorem or Dirac’s Theorem.
43
 Exercise 37 (p.645)
• Does the following graph have a Hamilton path? If so, find such a
path. If it does not, give an argument to show why no such path
exists.

a d
c f

b e

44
 Exercise 37 (p.645)
• Solution:
• This graph has the Hamilton path a, b, c, f, d, e.
This simple path hits each vertex once.

a d
c f

b e

Question: Does the above graph have Hamilton Circuit? Explain.

45