Graphs and Trees

Basic Terminology
Graph
• A graph G = (V ,E) consists of V , a nonempty set
of vertices (or nodes) and E, a set of edges. Each
edge has either one or two vertices associated
with it, called its endpoints.
• An edge is said to connect its endpoints.
• A graph with an infinite vertex set or an infinite
number of edges is called an infinite graph,
• a graph with a finite vertex set and a finite edge
set is called a finite graph
Types of Graphs
• Directed Graph (Diagraph)
• Undirected Graph
• Weighted Graphs
Undirected Graph
• Null graph
• Simple Graph
• Complete Graph
• Cyclic Graph
• Bipartite Graph
Null Graph-
A graph which contains only isolated node is called a null graph
i.e. set of edges in a null graph is empty.
Null graph is denoted on 'n' vertices by Nn.
Simple graph
• A graph which has neither loops nor multiple
edges i.e. where each edge connects two
distinct vertices and no two edges connects
the same pair of vertices is called a simple
graph.
Multigraph & Psuedograph
• Any graph which contains some multiple edges is called
a multigraph. In a multigraph, no loops are allowed.
• A graph in which loops and multiple edges are allowed is
called psuedograph.
Complete Graph
• A simple graph G is said to be complete if every vertex in G is
connected with every other vertex i.e. if G contains exactly
one edge between each pair of distinct vertices. Complete
graph is denoted on 'n' vertices bt Kn. Kn has exactly n(n-1) /2
edges.
Regular Graph
• A graph in which all the vertices are of equal degree is called
a regular graph. If the degree of each vertex is r, then the
graph is called a regular graph of degree r.
• Every null graph is a regular graph of degree zero and a
complete graph Kn is a regular graph of degree n-1.
Cyclic Graph-
• A graph with continuous sequence of vertices and edges is
called a cyclic graph.
• Cyclic graph is denoted on 'n' vertices bt Cn where n >=3
Wheel Graph

• A graph formed by adding a vertex inside a cycle and connecting it to every other vertex is known as wheel
graph.

• Wheel graph is denoted on 'n' vertices bt Wn where n>=3.

Bipartite Graph-
• A graph G=(V,E) is a bipartite if the vertex set V can be
partitioned into two subsets V1 and V2 such that every edge
in E connects a vertex in V1 and a vertex in V2 ( no edge in G
connects either two vertices in V1 or two vertices in V2) is
called a bipartite graph. A bipartite graph can have no loop.
Complete Bipartite Graph

• A graph where a set of vertices of a graph can be partitioned into two subesets

in such a way that no pair of vertices in the same set are adjacent to each other

and every vertex of first set is adjacent to the second set.

Concepts of Graph
• Complement of a graph is a graph will same number of vertices with the
property that if edges are present in the original graph there wont be any
edge in the complement and vice versa. A graph and its complement
together would give a complete graph.

• Order of a Graph- Order of a graph is defined as the number of

vertices present in the graph.
Isomorphism of Graphs

• Two graphs are said to be isomorphic if there exists a bijective

function from the set of vertices of the first graph to the set of
vertices of the second graph in such a way that the adjacency
relation (if 2 vertices are adjacent, then their images are also
adjacent) is maintained.
Handshaking Theorem
• Handshaking theorem states that the sum of degrees of the
vertices of a graph is twice the number of edges.If G=(V,E) be
a graph with E edges,then- Σ degG(V) = 2E
• Proof-
• Since the degree of a vertex is the number of edges
incident with that vertex, the sum of degree counts the total
number of times an edge is incident with a vertex. Since every
edge is incident with exactly two vertices,each edge gets
counted twice,once at each end. Thus the sum of the degrees
is equal twice the number of edges.

• -> This theorem applies even if multiple edges and loops are
present. The theorem holds this rule that if several people
shake hands, the total number of hands shake must be even
that is why the theorem is called handshaking theorem.
Some Representations for Graph
• Adjacency Matrices
• Incidence matrices
– Represent the incidence matrix for given graph.

Incidence Matrix
Isomorphism of Graph
• The simple graphs G1 = (V1,E1) and G2 = (V2,E2) are
isomorphic if there exists a oneto-one and onto
function f from V1 to V2 with the property that a and b
are adjacent in G1 if and only if f (a) and f (b) are
adjacent inG2, for all a and b in V1. Such a function f is
called an isomorphism.Two simple graphs that are not
isomorphic are called nonisomorphic.
Show that the graphs G = (V ,E) and H = (W, F),
displayed in Figure 8, are isomorphic.

The function f with f (u1) = v1, f (u2) = v4, f (u3) = v3, and f (u4) = v2 is a
oneto- one correspondence between V and W. To see that this
correspondence preserves adjacency,
• note that adjacent vertices in G are u1 and u2, u1 and u3, u2 and u4, and
u3 and u4, and each of the
• pairs f (u1) = v1 and f (u2) = v4, f (u1) = v1 and f (u3) = v3, f (u2) = v4 and f
(u4) = v2, and f (u3) = v3 and f (u4) = v2 consists of two adjacent vertices
in H.
Determine wheather the graphs are
isomorphic or not
1. Not Isomorphic

2.

Isomorphic
• Both G and H have six vertices and seven edges. Both have four
vertices of degree two and two vertices of degree three.

• arbitrarily set f (u1) = v6. [If we found that this choice did not lead to
isomorphism, we would then try f (u1) = v4.]. We arbitrarily set f (u2)
= v3. Continuing in this way, we set f (u3) = v4, f (u4) = v5, f (u5) = v1,
and f (u6) = v2.We now have a one-to-one correspondence between
the vertex set of G and the vertex set of H, namely, f (u1) = v6, f (u2) =
v3, f (u3) = v4, f (u4) = v5, f (u5) = v1, f (u6) = v2.
• cut vertices (or articulation points): Sometimes the removal
from a graph of a vertex and all incident edges produces a
subgraph with more connected components. Such vertices
are called cut vertices (or articulation points).
• The removal of a cut vertex from a connected graph produces
a subgraph that is not connected.
• cut edge or bridge: an edge whose removal produces a graph
with more connected components than in the original graph is
called a cut edge or bridge.
• Ex. in a graph representing a computer network, a cut vertex
and a cut edge represent an essential router and an essential
link that cannot fail for all computers to be able to
communicate.
• Find the cut vertices and cut edges in the graph G1 shown in
Figure

• The cut vertices of G1 are b, c, and e. The removal of one of

these vertices (and its adjacent edges) disconnects the graph.
• The cut edges are {a, b} and {c, e}. Removing either one of these
edges disconnects G1.
• Not all graphs have cut vertices. For example, the complete
graph Kn, where n ≥ 3, has no cut vertices. When you remove a
vertex from Kn and all edges incident to it, the resulting
subgraph is the complete graph Kn−1, a connected graph.
Connected graphs without cut vertices are called nonseparable
graphs,
• A subset V of the vertex set V of G = (V ,E) is a vertex cut, or
separating set, if G − V’ is disconnected.

• the set {b, c, e} is a vertex cut with three vertices,

Counting paths in between two vertices
• How many paths of length four are there from a to d in the simple
graph G

• Hence, the number of paths of length four from a to d is the (1,

4)th entry of A4.

• there are exactly eight paths of length four from a to d. By

inspection of the graph, we see that a, b, a, b, d; a, b, a, c, d; a, b,
d, b, d; a, b, d, c, d; a, c, a, b, d; a, c, a, c, d; a, c, d, b, d; and a, c, d,
c, d are the eight paths of length four from a to d.
Euler path and Euler Circuit
• An Euler circuit in a graph G is a simple circuit containing
every edge of G. An Euler path in G is a simple path containing
every edge of G.
• 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
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 H1 nor H3 has an Euler circuit.H3 has an Euler
path, namely, c, a, b, c, d, b, but H1 does not.

• A connected multigraph with at least two vertices has an

Euler circuit if and only if each of its vertices has even degree.
Algorithm to construct Euler Circuit
A connected multigraph has an Euler path but not an
Euler circuit if and only if it has exactly two vertices of
odd degree.

• G1 contains exactly two vertices of odd degree, namely, b and

d. 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.
Hamilton Paths and Circuits

• A simple path in a graphGthat passes through every

vertex exactly once is called a Hamilton path, and a
simple circuit in a graph G that passes through every
vertex exactly once is called a Hamilton circuit.
• That is, the simple path x0, x1, . . . , xn−1, xn in the
graph G = (V ,E) is a Hamilton path if V = {x0, x1, . . . ,
xn−1, xn} and xi = xj for 0 ≤ i < j ≤ n, and the simple
circuit x0, x1, . . . , xn−1, xn, x0 (with n > 0) is a
Hamilton circuit if x0, x1, . . . , xn−1, xn is a Hamilton
path.
• 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.
• A complete graph Kn has a Hamilton circuit
whenever n ≥ 3.
• 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.
• If G is a simple graph with n vertices with n ≥ 3
such that deg(u) + deg(v) ≥ n for every pair of
nonadjacent vertices u and v in G, then G has a
Hamilton circuit.
Single-Source Shortest Path Problem

Single-Source Shortest Path Problem - The

problem of finding shortest paths from a source
vertex v to all other vertices in the graph.
Dijkstra's algorithm
Dijkstra's algorithm - is a solution to the single-source
shortest path problem in graph theory.

Works on both directed and undirected graphs. However,

all edges must have nonnegative weights.

Input: Weighted graph G={E,V} and source vertex v∈V,

such that all edge weights are nonnegative

Output: Lengths of shortest paths (or the shortest paths

themselves) from a given source vertex v∈V to all other
vertices
Approach
• The algorithm computes for each vertex u the distance to u
from the start vertex v, that is, the weight of a shortest path
between v and u.
• the algorithm keeps track of the set of vertices for which the
distance has been computed, called the cloud C
• Every vertex has a label D associated with it. For any vertex u,
D[u] stores an approximation of the distance between v and u.
The algorithm will update a D[u] value when it finds a shorter
path from v to u.
• When a vertex u is added to the cloud, its label D[u] is equal to
the actual (final) distance between the starting vertex v and
vertex u.
37
Example: Initialization

Distance(source) = 0 0 ∞ Distance (all vertices but

A
2
B source) = ∞

4 1 3 10

2 2 ∞
∞ C D E

5 8 ∞ 4 6

1
F G

∞ ∞

Pick vertex in List with minimum distance.

38
Example: Update neighbors' distance

0 2
2
A B

4 1 3 10

2 2 ∞
∞ C D E

5 8 1 4 6

Distance(B) = 2 1
F G
Distance(D) = 1
∞ ∞

39
Example: Remove vertex with minimum
distance

0 2
2
A B

4 1 3 10

2 2 ∞
∞ C D E

5 8 1 4 6

1
F G

∞ ∞

Pick vertex in List with minimum distance, i.e., D

40
Example: Update neighbors

0 2
2
A B

4 1 3 10

2 2
3 C D E 3

5 8 1 4 6

Distance(C) = 1 + 2 = 3 1
F G
Distance(E) = 1 + 2 = 3
Distance(F) = 1 + 8 = 9 9 5
Distance(G) = 1 + 4 = 5

41
Example: Continued...
Pick vertex in List with minimum distance (B) and update neighbors
0 2
2
A B

4 1 3 10

2 2
3 C D E 3

5 8 1 4 6
Note : distance(D) not
1
F G updated since D is already
known and distance(E) not
9 5 updated since it is larger
than previously computed

42
Example: Continued...
Pick vertex List with minimum distance (E) and update neighbors

0 2
2
A B

4 1 3 10

2 2
3 C D E 3

5 8 1 4 6

1
F G
No updating
9 5

43
Example: Continued...
Pick vertex List with minimum distance (C) and update neighbors

0 2
2
A B

4 1 3 10

2 2
3 C D E 3

5 8 1 4 6

Distance(F) = 3 + 5 = 8 1
F G

8 5

44
Example: Continued...
Pick vertex List with minimum distance (G) and update neighbors

0 2
2
A B

4 1 3 10

2 2
3 C D E 3

5 8 1 4 6

1
F G
Previous distance
6 5
Distance(F) = min (8, 5+1) = 6

45
Example (end)

0 2
2
A B

4 1 3 10

2 2
3 C D E 3

5 8 1 4 6

1
F G

6 5
Pick vertex not in S with lowest cost (F) and update neighbors

46
Another Example
Another Example
Another Example
Another Example
Another Example
Another Example
Another Example
Another Example
Another Example
Traveling Salesperson Problem
• A traveling salesperson wants to visit each of n
cities exactly once and return to his starting
point.
• The following table shows the three different Hamilton
circuits and their weights:

• Thus we see that the circuit a-c-b-d-a (or the same circuit
starting at some other point but traversing the vertices in the
same or exactly opposite order) is the one with minimum
total weight.
Planar Graph
• A graph is called planar if it can be drawn in the plane without
any edges crossing, Such a drawing is called a planar
representation of the graph.
Is this a planar graph

• note that there is no way to place the final vertex v6 without forcing
a crossing.
• Application of Planarity of graphs plays an important role in the
design of electronic circuits
Euler’s Theorem
• Let G be a connected planar simple graph with
e edges and v vertices. Let r be the number of
regions in a planar representation of G.
Then r = e − v + 2.
– Proof:
• The relationship r1 = e1 − v1 + 2 is true for G1, because e1 = 1, v1 =
2, and r1 = 1

• Now assume that rk = ek − vk + 2. Let {ak+1, bk+1} be the edge that

is added to Gk to obtain Gk+1.
• In the first case, both ak+1 and bk+1 are already in Gk. These two
vertices must be on the boundary of a common region R, or else it
would be impossible to add the edge {ak+1, bk+1} to Gk without
two edges crossing (and Gk+1 is planar).
• The addition of this new edge splits R into two regions.
Consequently, in this case, rk+1 = rk + 1, ek+1 = ek + 1, and vk+1 =
vk. Thus, each side of the formula relating the number of regions,
edges, and vertices increases by exactly one, so this formula is still
true.
• In other words, rk+1 = ek+1 − vk+1 + 2.
• In the second case, one of the two vertices of the new edge is
not already in Gk.
• Suppose that ak+1 is in Gk but that bk+1 is not. Adding this
new edge does not produce any new regions, because bk+1
must be in a region that has ak+1 on its boundary.
Consequently, rk+1 = rk.
• Moreover, ek+1 = ek + 1 and vk+1 = vk + 1. Each side of the
formula relating the number of regions, edges, and vertices
remains the same, so the formula is still true. In other words,
rk+1 = ek+1 − vk+1 + 2.
Corollary
• If G is a connected planar simple graph with e edges and v
vertices, where v ≥ 3, then e ≤ 3v − 6.
– Ex. The graph K5 has five vertices and 10 edges. However, the
inequality e ≤ 3v − 6 is not satisfied for this graph because e = 10 and
3v − 6 = 9. Therefore, K5 is not planar.
• If G is a connected planar simple graph, then G has a vertex of
degree not exceeding five.
• If a connected planar simple graph has e edges and v vertices
with v ≥ 3 and no circuits of length three, then e ≤ 2v − 4.
– Ex. K3,3 has no circuits of length three (this is easy to see because it is
bipartite), Corollary 3 can be used. K3,3 has six vertices and nine edges.
Because e = 9 and 2v − 4 = 8, Corollary 3 shows that K3,3 is nonplanar.
Homomorphic Graph
• Two graphs G and H are said to be
homomorphic if one can be obtained from
other by merging of edges or addition of
vertices.
Kuratowski’s Theorem
• A graph is nonplanar if and only if it contains a
subgraph homeomorphic to K3,3 or K5.

• It is clear that a graph containing a subgraph

homeomorphic toK3,3 orK5 is nonplanar.
However, the proof of the converse, namely
that every nonplanar graph contains a
subgraph homeomorphic to K3,3 or K5, is
complicated and will not be given here.
• The subgraph H of the Petersen graph obtained by
deleting b and the three edges that have b as an
endpoint, is homeomorphic to K3,3, with vertex sets {f, d,
j} and {e, i, h}, because it can be obtained by a sequence
of elementary subdivisions, deleting {d, h} and adding {c,
h} and {c, d}, deleting {e, f } and adding {a, e} and {a, f },
and deleting {i, j } and adding {g, i} and {g, j}.
• Hence, the Petersen graph is not planar.
Graph Coloring
• A coloring of a simple graph is the assignment
of a color to each vertex of the graph so that
no two adjacent vertices are assigned the
same color.
• The chromatic number of a graph is the least
number of colors needed for a coloring of this
graph. The chromatic number of a graph G is
denoted by χ(G).
• THE FOUR COLORTHEOREM The chromatic
number of a planar graph is no greater than four.
• What is the chromatic number of Kn?
• chromatic number of Kn is n. That is, χ(Kn) = n. (Recall that Kn is not planar
when n ≥ 5, so this result does not contradict the four color theorem.) A
coloring of K5 using five colors

• What is the chromatic number of the complete bipartite graph Km,n, where
m and n are positive integers?

• χ(Km,n) = 2. This means that we can color the set of m vertices with one color
and the set of n vertices with a second color.
• Because edges connect only a vertex from the set of m vertices and a vertex
from the set of n vertices, no two adjacent vertices have the same color. A
coloring of K3,4 with two colors
• What is the chromatic number of the graph Cn, where n ≥ 3?

• In general, two colors are needed to color Cn when n is even.

• n is odd and n > 1, the chromatic number of Cn is 3.
• χ(Cn) = 2 if n is an even positive integer with n ≥ 4 and
χ(Cn) = 3 if n is an odd positive integer with n ≥ 3.

• Application of graph coloring can be scheduling of exams so

that no students will have two exams on same day.