�ݺ�ߣ

There is a simple path between every pair of distinct
vertices of a connected undirected graph.
• Suppose a and b are two distinct vertices of the connected undirected
graph G =(V, E).
• we know that G is connected so by definition there is at least one path
between a and b .
• Let x0, x1, …, xn, where x0 = a and xn = b, be the vertex sequence of a path
of a least length.
• Now if this path of the least length is not simple then we have xi = xj, for
some i and j with 0 £ i < j.
• This implies that there is a path from a to b of shorter length with the
vertex sequence x0, x1, …, xi, …, xj+1, …, xn obtained by removing the
edges corresponding to the vertex sequence xi+1, …, xj.
• This shows that there is a simple path.

• Cut vertices (articulation points) are those vertices in the graph
whose removal along with the edges incident on them produces
subgraph with more connected components than in the original
graph.
• Cut edge (bridge) is an edge whose removal produces a graph with
more connected components than in the original graph.

Euler Paths and Circuits
• 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.
• Example:
• Find the Euler path or circuit in the following graphs
• No Euler circuit exist,
• but the Euler path is
• 1,2,5,1,3,5,4,3,5,2,4

• The Euler circuit is
• 1,2,3,6,9,8,7,4,5,8,6,5,2,4,1

Necessary and Sufficient Conditions for Euler
Circuits and Paths
• Theorem 5:
• A connected multigraph has an Euler circuit if and only if each of its
vertices has even degree.
• Proof:
• Take a connected multigraph G =(V, E) where V and E are finite. We
can prove the theorem in two parts.

• Theorem 6:
• A connected multigraph has an Euler path but not Euler circuit if and
only if it has exactly two vertices of odd degree.

• Find Euler path or circuit?
• In the above graph, all the vertices have even degree, hence there is an
Euler circuit.
• The Euler circuit is
1,2,3,4,5,10,15,14,13,12,11,6,13,8,9,14,12,7,8,3,10,9,4,2,7,6,1

Hamilton paths
• A path x0, x1, …, xn-1, xn in the graph G = (V, E) is called Hamilton path if
V ={x0, x1, …, xn-1, xn} and xi≠ xj for 0 ≤ i < j ≤n.
• A circuit x0, x1, …, xn-1, xn, x0, with n > 1, in a graph G =(V, E) is a
Hamilton circuit if x0, x1, …, xn-1, xn is a Hamilton path.
• A graph with a vertex of degree one cannot have a Hamilton circuit.
• If a vertex in a graph has degree 2, then both edges incident with this
vertex must be part of Hamilton circuit.

• Example:
Find Hamilton circuit from the following graph if exists? What about
Hamilton path?
In graph (a) there is no Hamilton circuit since
the node c has degree 2 and both the edges
from it must be in Hamilton circuit, which is not
possible. One of the Hamilton path in the graph
(a) is a, b, c, d, e.

• In graph (b) we can find Hamilton circuit, the circuit can be 1,2,3,5,6,
9,8,7,4,1. Since there is circuit we can have path also.

• Theorem 7: 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 8: 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 nonadjacent vertices u and v in G, then G
has a Hamilton path.

Planar graphs
• A graph is called a planar if it can be drawn in the plane without any
edges crossing.
• Such drawing is called a planar representation of the graph.
• Example:
• Draw the graph below as planar representation of the graph.

• Theorem 9: Euler’s Formula
• 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.
• Example:
• Suppose that a connected planar graph has 30 edges. If a planar representation
of this graph divides the plane into 20 regions, how many vertices does this graph
have?
• Solution:
• We have, r = 20, e = 30,
• so by Euler’s formula we have
• v = e – r + 2 = 30 – 20 + 2 = 12.
• So the number of vertices is 12.

• Corollary 1:
• If G is a connected planar simple graph with e edges and v vertices
where v>=3, then e<=3v – 6.
• Corollary 2:
• If G is a connected planar simple graph, then G has a vertex of degree
not exceeding five.
• Corollary 3:
• 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.

• If a graph is planar, any graph obtained by removing an edge {u, v}
and adding a new vertex w together with edges {u, w} and {w, v}. Such
an operation is called an elementary subdivision.
• The graphs G1 = (V1, E1) and G2 = (V2, E2) are called homeomorphic
if they can be obtained from the same graph by a sequence of
elementary subdivisions.
• Example:
• The below example graphs are homeomorphic to the third graph.

• Theorem 10: Kuratowski’s Theorem
• A graph is nonplanar if and only if it contains a subgraph
homeomorphic to K3,3 or K5.
• Example:
• Determine whether the following graph is planar or not?

• Above we saw that the graph is homeomorphic to K5, the given 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.
• A chromatic number of a graph is the least number of colors needed
for a coloring of this graph.
• Theorem 11:The Four Color Theorem
• The chromatic number of a planar graph is no greater than four.
• To show the chromatic number of a graph as k we must show that the
graph can be colored using k colors and the given graph cannot be
colored using fewer than k colors

• Example#1
• Construct the dual graph for the map shown. Then find the number of
colors needed to color the map so that no two adjacent regions have
the same color.

• We can color the graph with at most 2 colors as shown in the graph.
Take R and G as red and green

• Example#2
• Find the chromatic number of the graph below.

• Lets start with vertex 1, it has adjacent vertices as 2, 3, 4, 5, 6, 9 so using
only 2 colors would suffice for the graph having the edges from 1 to its
adjacent vertices.
• However since 9 has its adjacent vertices as 1, 2, 3, 4 we cannot just color
the above graph with 2 colors because at least 1, 2 and 9 must have
different colors.
• Trying with 3 colors we found that at least 1, 2, 3, and 9 must have different
colors.
• So trying with four colors we can color the graph. Hence the chromatic
number of the above graph is 4. possible coloring is shown in the figure
below

�ݺ�ߣ

Ds lec 5_chap4

More Related Content

Ds lec 5_chap4