Welcome to !

Discrete Structures

1
GRAPHS

2
 GRAPH

A graph is a non-empty set of points called vertices and a set of line

segments joining pairs of vertices called edges.
Formally, a graph G consists of two finite sets:
(i) A set V=V(G) of vertices (or points or nodes)
(ii)A set E=E(G) of edges; where each edge corresponds to a pair of
vertices.

The graph G with

V(G) = {v1, v2, v3, v4, v5} and
E(G) = {e1, e2, e3, e4, e5, e6}

3
 SOME TERMINOLOGY

1. An edge connects either one or two vertices called its endpoints (edge e1
connects vertices v1 and v2 described as {v1, v2} i.e v1 and v2 are the endpoints
of an edge e1).
2. An edge with just one endpoint is called a loop. Thus a loop is an edge that
connects a vertex to itself (e.g., edge e6 makes a loop as it has only one endpoint
v3).
3. Two vertices that are connected by an edge are called adjacent; and a vertex
that is an endpoint of a loop is said to be adjacent to itself.
4. An edge is said to be incident on each of its endpoints(i.e. e1 is incident on v1
and v2 ).
5. A vertex on which no edges are incident is called isolated (e.g., v5)
6. Two distinct edges with the same set of end points are said to be parallel (i.e.
e2 & e3).

4
 EXAMPLE

Define the following graph formally by specifying its vertex set, its edge set,
and a table giving the edge endpoint function.

SOLUTION:
Vertex Set = {v1, v2, v3, v4}
Edge Set = {e1, e2, e3}
Edge - endpoint function is:

5
 Task

For the graph shown below

(i) find all edges that are incident on v1;
(ii)find all vertices that are adjacent to v3;
(iii)find all loops;
(iv)find all parallel edges;
(v)find all isolated vertices;

6
DRAWING PICTURE FOR A GRAPH

Draw picture of Graph H having vertex set {v1, v2, v3, v4, v5}
and edge set {e1, e2, e3, e4} with edge endpoint function

7
 SOLUTION

Given V(H) = {v1, v2, v3, v4, v5}

and E(H) = {e1, e2, e3, e4}
with edge endpoint function

8
 SIMPLE GRAPH

A simple graph is a graph that does not have any loop

or parallel edges.

9
 EXERCISE

Draw all simple graphs with the four vertices {u, v, w, x} and two
edges, one of which is {u, v}.
SOLUTION:
There are C(4,2) = 6 ways of choosing two vertices from 4
vertices. These edges may be listed as:
{u,v},{u,w},{u,x},{v,w}, {v,x},{w,x}
One edge of the graph is specified to be {u,v}, so any of the
remaining five from this list may be chosen to be the second edge.
This required graphs are:

10
11
 DEGREE OF A VERTEX

Let G be a graph and v a vertex of G. The degree of v, denoted

deg(v), equals the number of edges that are incident on v,
with an edge that is a loop counted twice.
Note:(i)The total degree of G is the sum of the degrees of
all the vertices of G.
(ii) The degree of a loop is counted twice.

12
Example

13
 THE HANDSHAKING THEOREM

If G is any graph, then the sum of the degrees of all the vertices of G equals twice the
number of edges of G.
Specifically, if the vertices of G are v1, v2, …, vn, where n is a positive integer, then
the total degree of G = deg(v1) + deg(v2) + … + deg(vn)
The total degree of G = 2 . (the number of edges of G)
PROOF:
Each edge “e” of G connects its end points vi and vj. This edge, therefore
contributes 1 to the degree of vi and 1 to the degree of vj.
If “e” is a loop, then it is counted twice in computing the degree of the vertex on which
it is incident.
Accordingly, each edge of G contributes 2 to the total degree of G.
Thus,
the total degree of G = 2. (the number of edges of G)
COROLLARY:
The total degree of G is an even number

14
THE HANDSHAKING THEOREM

15
 EXERCISE

 Draw a graph with the specified properties or explain why no such

graph exists.
(i) Graph with four vertices of degrees 1, 2, 3 and 3
(ii) Graph with four vertices of degrees 1, 2, 3 and 4
(iii)Simple graph with four vertices of degrees 1, 2, 3 and 4

16
 SOLUTION

(i) Total degree of graph = 1 + 2 + 3 + 3 = 9 an odd integer

Since, the total degree of a graph is always even, hence no such graph is
possible.
Note:As we know that “for any graph,the sum of the degrees of all the vertices
of G equals twice the number of edges of G or the total degree of G is an even
number”.

17
 SOLUTION

(iii) Suppose there was a simple graph with four vertices of degrees 1, 2, 3, and 4.
Then the vertex of degree 4 would have to be connected by edges to four
distinct vertices other than itself because of the assumption that the graph is
simple (and hence has no loop or parallel edges.) This contradicts the
assumption that the graph has four vertices in total. Hence there is no simple
graph with four vertices of degrees 1, 2, 3, and 4, so simple graph is not
possible in this case

18
 Task

 Suppose a graph has vertices of degrees 1, 1, 4, 4 and 6. How many

edges does the graph have?

In a group of 15 people, is it possible for each person to have exactly

3 friends?

19
 COMPLETE GRAPH

A complete graph on n vertices is a simple graph in which each vertex

is connected to every other vertex and is denoted by Kn (Kn means
that there are n vertices).
The following are complete graphs K1, K2,K3, K4 and K5.

20
COMPLETE GRAPH

21
 REGULAR GRAPH

A graph G is regular of degree k or k-regular if every vertex of

G has degree k. In other words, a graph is regular if every vertex
has the same degree.
Following are some regular graphs.

22
EXERCISE:
Draw two 3-regular graphs with six vertices.

23
 BIPARTITE GRAPH

A simple graph G is called bipartite if its vertex set V

can be partitioned into two disjoint sets V1 and V2 such
that every edge in the graph connects a vertex in V1 and
a vertex in V2 (so that no edge in G connects either two
vertices in V1 or two vertices in V2). When this
condition holds, we call the pair (V1, V2) a bipartition
of the vertex set V of G.

24
 BIPARTITE GRAPH

A bipartite graph G is a simple graph whose vertex set can be

partitioned into two mutually disjoint non empty subsets A and B
such that the vertices in A may be connected to vertices in B, but
no vertices in A are connected to vertices in A and no vertices in
B are connected to vertices in B. The following are bipartite
graphs

25
 DETERMINING BIPARTITE
GRAPHS
The following labeling procedure determines whether a graph is
bipartite or not.
1. Label any vertex a
2. Label all vertices adjacent to a with the label b.
3. Label all vertices that are adjacent to a vertex just labeled b with
label a.
4. Repeat steps 2 and 3 until all vertices got a distinct label (a bipartite
graph) or there is a conflict i.e., a vertex is labeled with a and b (not a
bipartite graph).

26
EXERCISE

27
Solution

28
 COMPLETE BIPARTITE GRAPH
A complete bipartite graph on (m+n) vertices denoted Km,n is a
simple graph whose vertex set can be partitioned into two mutually
disjoint non empty subsets A and B containing m and n vertices
respectively, such that each vertex in set A is connected (adjacent)
to every vertex in set B, but the vertices within a set are not
connected.

29
 DEFINITIONS

Let G be a graph and let v and w be vertices in graph G.

30
PATHS AND CIRCUITS

31
Summary

32
 EXERCISE

In the graph below, determine whether the following walks are

paths, simple paths, closed walks, circuits, simple circuits, or are just
walks.

(a) v1e2v2e3v3e4v4e5v2e2v1e1v0
(b) v1v2v3v4v5v2
(c) v4v2v3v4v5v2v4
(d) v2v1v5v2v3v4v2
(e) v0v5v2v3v4v2v1
(f) v5v4v2v1
33
CONNECTEDNESS

34
 EULER CIRCUITS

DEFINITION:
Let G be a graph. An Euler circuit for G is a circuit that contains
every vertex and every edge of G. That is, an Euler circuit for G is
sequence of adjacent vertices and edges in G that starts and ends at
the same vertex uses every vertex of G at least once, and used every
edge of G exactly once.
THEOREM:
A graph G has an Euler circuit if, and only if, G is connected and
every vertex of G has an even degree.

35
KONIGSBERG BRIDGES PROBLEM

We try to solve Konigsberg bridges problem by Euler method.

Here deg(a)=3,deg(b)=3,deg(c)=3 and deg(d)=5 as the vertices have odd
degree so there is no possibility of an Euler circuit.

36
KONIGSBERG BRIDGES PROBLEM

37
 EULER PATH

DEFINITION:
Let G be a graph and let v and w be two vertices of G. An
Euler path from v to w is a sequence of adjacent edges and
vertices that starts at v, end and w, passes through every
vertex of G at least once, and traverses every edge of G
exactly once.
COROLLARY
Let G be a graph and let v and w be two vertices of G. There
is an Euler path from v to w if, and only if, G is connected, v
and w have odd degree and all other vertices of G have even
degree.

38
 HAMILTONIAN CIRCUITS
DEFINITION:
Given a graph G, a Hamiltonian circuit for G is a simple circuit that includes
every vertex of G. That is, a Hamiltonian circuit for G is a sequence of adjacent
vertices and distinct edges in which every vertex of G appears exactly once.
EXERCISE:
Find Hamiltonian Circuit for the following graph.

SOLUTION:
The Hamiltonian Circuit for the following graph is:
abdefcgha
Another Hamiltonian Circuit for the following graph could be:
abcdefgha

39
 PROPOSITION
If a graph G has a Hamiltonian circuit then G has a sub-graph H
with the following properties:
1. H contains every vertex G
2. H is connected
3. H has the same number of edges as vertices
4. Every vertex of H has degree 2

40
PROPOSITION

41
ASSIGNMENT

42
Thank You

43