Welcome to !
Discrete Structures
1
PLANER GRAPHS
2
PLANER GRAPHS
INTRODUCTION:
we will study that whether any graph can be drawn in the plane (means
“a flat surface”) without crossing any edges.
It is a graph on 4 vertices and written as K4. Each vertex is connected
to every other vertex.
Note it that here edges are crossed. Also the above graph can also be
drawn as
3
PLANER GRAPH
In this graph, note it that each vertex is connected to every
other vertex, but no edge is crossed.
Note: The graphs shown above are complete graphs with four
vertices (denoted by K4).
4
PLANER GRAPH
DEFINITION:
A graph is called planar if it can be drawn in the plane without any
edge crossed (crossing means the intersection of lines). Such a
drawing is called a plane drawing of the graph.
OR
You can say that a graph is called planar in which the graph
crossing number is “0”.
5
The graphs given above are planar .In the first figure edges are
crossed but it can be redrawn in second figure where edges are
not crossed, so called planar.
It is also a graph on 4 vertices
(written as K4) with no edge crossed,
hence called planar.
Note: The graphs given above are also complete graphs (except
second; are those where each vertex is connected to every other
vertex) on 4 vertices and is written as K4 .
Note: Complete graphs are planar only for n ≤ 4. 6
EXAMPLE
Show that the graph below is planar.
SOLUTION:
This graph has 8 vertices and 12 edges, and is called 3-cube and
is denoted Q3.
The above representation includes many "edge crossing." A plane
drawing of the graph in which no two edges cross is possible and
shown below.
7
Exercise
Determine whether the graph below is planar. If so, draw it so that no
edges cross.
SOLUTION:
The graph given above is bipartite graph denoted by K3. It also has a
circuit afcebda. This graph can be re-drawn as
8
9
10
DEFINITION:
A plane drawing of a planar graph divides the plane into regions, including an
unbounded region, called faces.
The unbounded region is called the infinite face.
Here we have 6 faces,7 vertices and 10 edges.f6 is the unbounded region or called the
infinite face because f6 is outside of the graph.
In this graph, it has 8 faces,9 vertices and 14 edges. Here f5 is the infinite face or
unbounded region.
11
EULER’S FORMULA
THEOREM:
Let G be a connected planar simple graph with e edges and v vertices. Let
f be the number of faces in a plane drawing of G. Then f = e – v + 2
EXERCISE:
Suppose that a connected planar simple graph has 30 edges. If a plane
drawing of this graph has 20 faces, how many vertices does this graph
have?
SOLUTION:
Given that e = 30, and f = 20. Substituting these values in the Euler’s
Formula f = e – v + 2 , we get
20 = 30 – v + 2
Hence,
v = 30 – 20 + 2 = 12
12
GRAPH COLORING
13
HOW TO DRAW A GRAPH FROM A MAP
1. Each map in the plane can be represented by a graph.
2. Each region is represented by a vertex (in 1st map as there
are 7 regions, so 7 vertices are used in drawing a graph,
similarly we can see 2nd map).
3. If the regions connected by these vertices have the common
border, then edge connect two vertices.
4. Two regions that touch at only one point are not adjacent.
So apply these rules, we have (first graph drawn from first map
given above, second graph from second map).
14
DEFINITION
1. 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.
2. The chromatic number of a graph is the least (minimum) number of colors
for coloring of this graph.
EXAMPLE:
What is the chromatic number of the graphs G and H shown below?
15
SOLUTION
Clearly the chromatic number of G is 3 and chromatic number of H is 4(by
using the above definition).
In graph G, As vertices a, b and c are adjacent to each other so assigned
different colors. So we assign red color to vertex a, blue to b and green to
vertex c. Then no more colors we choose (due to above definition).Now vertex
d must be colored red because it is adjacent to vertex b(with blue color) and
c(with green color). And e must be colored green because it is adjacent to
vertex b(blue color) and vertex d(red color). And f must be colored blue as it is
adjacent to red and green color. At last,vertex g must be colored red as it is
adjacent to green and blue color.
Same process is used in Graph H.
16
Thank You
17