Graphs

Chapter 10

Kenneth Rosen, Discrete Mathematics and its Applications, 7th edition,

McGraw Hill 2012.
Chapter Summary
Graphs and Graph Models (10.1)
Graph Terminology and Special Types of
Graphs (10.2)
Representing Graphs and Graph Isomorphism
(10.3)
Connectivity (10.4)
Euler and Hamiltonian Graphs (10.5)
Shortest-Path Problems (10.6)
Planar Graphs (10.7)
Graphs and Graph Models
Section 10.1
History
 Basic ideas were introduced in the eighteenth
century by Leonard Euler (Swiss mathematician)

Euler was interested in solving the Königsberg bridge

problem (Town of Königsberg is in Kaliningrad,
Republic of Russia)

Graphs have several applications in many areas:

 Study of the structure of the World Wide Web
 Shortest path between 2 cities in a transportation
network
 Molecular chemistry

4
 Introduction to Graphs
Definition 1
 A simple graph G = (V,E) consists of V, a
nonempty set of vertices, and E, a set of
unordered pairs of distinct elements of V
called edges. 1 3
Vertex
V = {1, 2, 3, 4, 5} Edge 2 (Node)
4
E = { {1,2}, {1,3}, {1,4}, {2,3}, {3,5}, {4,5} } 5
Example:

5
Introduction to Graphs
Definition 2:
Graphs that may have multiple edges
connecting the same vertices are called
multigraphs
When there are m different edges
associated to the same unordered pair of
vertices {u, v}, we also say that {u, v} is
an edge of multiplicity m
What is the multiplicity of
{Denver,Chicago}?

6
Introduction to Graphs
Definition 3:
 A pseudograph is a graph that
allows an edge to connect a vertex to itself.
Such edges are called loops

7
Introduction to Graphs
Definition 4
 A directed graph G = (V,E) consists of V,
a nonempty set of vertices, and E, a set of
ordered pairs of distinct elements of V called
directed edges (Arcs). 1
V = {1, 2, 3, 4,}
4
E = { (1,4),(2,1),(2,4),(4,2),(4,3) } 2
3
Note that (u,v)≠(v,u)
This type of graphs can be used to model
situations where direction is relevant. For
example, roads, relations in social app networks: x
follows y is different from y follows x

8
Introduction to Graphs
Definition 4
 Directed graphs that may have multiple
directed edges are called directed multigraphs.
When there are m directed edges, each
associated to an ordered pair of vertices (u, v), we
say that (u, v) is an edge of multiplicity m.

9
Graph Taxonomy

10
 Modeling with graphs
Example: Influence of one person in society
A directed graph called an influence

graph is used to model this behavior

There is a directed edge from vertex a to

vertex b if the person represented by a

vertex a influences the person represented
by vertex b. The relation: x follows y in
social media apps is an example of this
type.

11
 Modeling with graphs
Example: Friendship Graphs
 Simple graphs can be used to represent

whether two people know each other, that is,

whether they are An undirected edge is used to
connect two people when these people know
each other. The relation: x is friend of y in social
media apps is an example of this type.

12
 Modeling with graphs
Example: Call Graphs
 Directed Multigraphs can be used can be used

to model telephone calls made in a network.

 They can be used also to model The World Wide

Web

Wikipedia web graph

13
Graph Terminology and
Special Types of Graphs
Section 10.2
 Graph Terminology (10.2)
Definition 1:
 Two vertices u and v in an undirected graph
G are called adjacent (or neighbors) in G if u and
v are endpoints of an edge e of G. Such an edge e
is called incident with the vertices u and v and e
is said to connect u and v. The set of all neighbors
of a vertex v, denoted by N (v), is called the
neighborhood of v. e1
v1 v3
Examples:
 v1 and v3 are adjacent. v2
 Edge e1=(v1 ,v3) is incident with v1 and v3v4
v5
 The neighborhood of v1 N(v1)={v2, v3, v4}

15
Graph Terminology
Definition 2:
 The degree of a vertex in an undirected graph is
the number of edges incident with it, except that a loop
at a vertex contributes twice to the degree of that
vertex. The degree of the vertex v is denoted by deg(v).

In G, deg(a) = 2, deg(b) = deg(c) = deg(f ) = 4, deg(d ) = 1, deg(e) =

3, and deg(g) = 0. The neighborhoods of these vertices are N (a) =
{b, f }, N (b) = {a, c, e, f }, N (c) = {b, d, e, f }, N (d) = {c}, N (e) =
{b, c, f }, N (f ) = {a, b, c, e}, and N (g) = ∅.
In H, deg(a) = 4, deg(b) = deg(e) = 6, deg(c) = 1, and deg(d ) = 5.
The neighborhoods of these vertices are N (a) = {b, d, e}, N (b) =
{a, b, c, d, e}, N (c) = {b}, N (d) = {a, b, e}, and N (e) = {a, b, d}. 16
Graph Terminology
Theorem 1:
The handshaking theorem
Let G = (V,E) be an undirected graph with m
edges. Then
2∨𝐸∨¿ ∑ deg(¿𝑣).¿
𝑣∈𝑉

(Note that this applies even if multiple edges & loops are
present.)
Example: How many edges are there in a graph
with 10 vertices each of degree six? Solution:
Because the sum of the degrees of the vertices is
6 · 10 = 60, it follows that 2m = 60 where m is
the number of edges. Therefore, |E|= 30.
17
 Graph Terminology
Definition 3:
 When (u,v) is an edge of the graph G with
directed edges, u is said to be adjacent to v and v
is said to be adjacent from u. The vertex u is
called the initial vertex of (u,v), and v is called
the terminal or end vertex of (u,v). The initial
vertex and terminal vertex of a loop are the same.
v e v
Example: 1 2

v1 is adjacent to v2
v2 is adjacent from v1
v1 is the initial vertex of e
v2 is the terminal vertex of e

18
 Graph Terminology
Definition 3:
 In directed graphs, the in-degree of a vertex
v, denoted deg-(v), is the number of edges with v as
their terminal vertex. The out-degree of v, denoted
by deg+(v), is the number of edges with v as their
initial vertex.
(Note that a loop at a vertex contributes 1 to both
the in-degree and the out-degree of this vertex)
Example: In
G: The out-
The in- degrees:
degrees deg − deg +
(a) = 4,
(a) = 2, deg+(b) = 1,
deg−(b) = 2, deg+(c) = 2,
deg (c) = 3,
− deg +
(d) = 2,
deg (d) = 2,
− deg +
(e) = 3,
19
− deg+(f ) = 0.
Graph Terminology
Theorem 3:
 Let G = (V,E) be a graph with directed
edges. Then,−
∑ deg (¿𝑣 )= ∑ deg +¿(¿𝑣 )=¿ 𝐸∨. ¿
¿¿
𝑣 ∈𝑉 𝑣∈𝑉

Example: In graph G of the last example,

=12
=12
Number of edges in G, |E|=12

20
Special Simple Graphs
Complete graph: A complete graph on n
vertices, denoted by Kn, is a simple graph that
contains exactly one edge between each pair of
distinct vertices

21
Special Simple Graphs
Cycles: They are denoted by Cn(n  3): they
consist of n vertices v1, v2, …, vn and edges {v1,
v2}, {v2, v3}, …, {vn, vn-1} and {vn, v1}

Wheels: They are denoted by Wn; they are

obtained by adding a vertex to the graphs Cn and
connect this vertex to all vertices

22
 Bipartite Graphs
Definition 5: A simple graph is called bipartite if
its vertex set V can be partitioned into 2 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 2 vertices in V1 or 2
vertices in V2). When this condition holds, we call the
pair (V1, V2) a bipartition of the vertex set V of G.

V1 V2

23
 Bipartite Graphs
Bipartite graphs often arise naturally when
modelling relations between two different
classes of objects,
Example: A graph of football players and clubs, with
an edge between a player and a club if the player
has played for that club, is a natural example of
an affiliation network,
Inter
Ronaldo
Milan

Juventus Messi

FC Barcelona Maradona
24
 Bipartite Graphs
Theorem 4: A graph is bipartite if and only if it is
possible to color the vertices of the graph with at most
2 colors so that no two adjacent vertices have the
same color v6 v1
C6
Example 1: Show that C is bipartite. v2
6 v5
 Proof:Color odd vertices in red
and even vertices %in blue. v4 v3

Example 2: K5 is not bipartite

 Proof: take any arbitrary three vertices
from K5 . Color them with red or Blue. Two of them at least
must have the same color, since we are allowed to use at
most 2 colors. But in K5, every pair is connected
so, we get 2 adjacent vertices which have the same
color and by the theorem, K5 can’t be bipartite. 25
Graph coloring for bipartite graphs
1- choose a starting vertex and color it.
2-Repeat
2.1 choose a colored vertex and color its neighbors with
the opposite color if they are not colored yet.
2.2 If any adjacent vertices have the same colors then
output Not bipartite and stop.
until every vertex is colored.
3- output bipartite.
Complete Bipartite Graphs
Definition: A complete bipartite graph Km,n
is a graph that has its vertex set partitioned
into two subsets V1 of size m and V2 of
size n such that there is an edge from every
vertex in V1 to every vertex in V2.
Representing Graphs and
Graph Isomorphism
Section 10.3
Section Summary
Adjacency Lists
Adjacency Matrices
Isomorphism of Graphs
Representing Graphs (10.3)
Adjacency list representation:
 Use adjacency list, which specifies the vertices
that are adjacent to each vertex of the graph

30
Representing Graphs (10.3)
Adjacency list representation for directed graph
is the same.
Initial Terminal
vertex vertex
1
1 4
4
2
2 1,4
3 3
4 2,3

31
 Representing Graphs
Adjacency Matrix Representation
The Adjacency Matrix A=(ai,j) of a graph
G=(V,E) with n vertices is an nXn matrix. Each
element of A is either 0 or 1, depending on the
adjacency of the nodes:

Example: Find the adjacency matrices of the

following graphs.
1 2 3 4 5
1 0 1 1 1 0 a c
1 3 2 1 0 1 0 0
b
2 3 1 1 0 0 1
4 4 1 0 0 0 1 a b c
5 5 0 0 1 1 0 a 0 1 0
b 0 0 1
The adjacency matrix of a simple
c 1 1 0
graph is symmetric 32
 TRADE-OFFS BETWEEN ADJACENCY LISTS AND
ADJACENCY MATRICES
Suppose you have a graph with |V|=1000 vertices.
How many entries does its adjacency matrix
contain?
 |V|2 =1000*1000=1000,000 entries.

How many entries does its adjacency list contain if

you assume that the average vertex degree is c?
 |V|*c= 1000*c entries
Adjacency list:
Use when graph contains relatively few edges. That is
when the average vertex degree is constant compared
to |V|
Adjacency Matrix
Otherwise use adjacency matrix
33
 Graph Isomorphism (10.3)
 Isomorphism of graphs

Is it possible to draw two

graphs in the same way? That
is, do the graphs have the same
structure when we ignore the
identities of their vertices.

Graphs having the same

structure share common
properties
v
1 v4

v
v3 2
34
Graph Isomorphism
Definition :
The simple graphs G1 = (V1,E1) and G2 = (V2,E2)
are isomorphic if there is a bijective function f
(bijection) from V1 to V2 with the property that w
and v are adjacent in G1 if and only if f(w) and
f(v) are adjacent in G2, for all w and v in V1. Such
a function f is called an isomorphism.
Example: In G=(V,E) and H=(W,F)
The function f with
f (u1) = v1 f (u2) = v4
f (u3) = v3 f (u4) = v2
is a one to-one correspondence between V and W
So G and H are isomorphic. Can you find another
isomorphism f? 35
Determining whether Two Simple Graphs are Isomorphic
 This task is difficult in general since there are n!
possible bijections between the vertex sets of two
simple graphs with n vertices. No algorithm can solve
this problem efficiently yet!
 We can show that two graphs are not isomorphic if we
can find a property only one of the two graphs has, but
that is preserved by isomorphism. Such property is
called a graph invariant.
 The number of vertices |V|, the number of edges |E|,
and the number of vertices of each degree are all
invariants under isomorphism.
 If any of these quantities differ in two simple graphs,
these graphs cannot be isomorphic. However, when
these invariants are the same, it does not necessarily
mean that the two graphs are isomorphic
36
Determining whether Two Simple Graphs are Isomorphic
G1 and H1 are not isomorphic. H1
has a vertex of degree one,
namely, e, whereas G1 has no
vertices of degree one
G1
H
1
11
G2 and H2 are not isomorphic.
Since they have different
numbers of edges
 G3 and H3 are isomorphic. G21 H
 f (u1) = v6 f (u2) = v3
21
 f (u3) = v4 f (u4) = v5
 f (u5) = v1 f (u6) = v2.

G31 H
37
31
Connectivity
Section 10.4
Section Summary
Paths
Connectedness in Undirected Graphs
Vertex Connectivity and Edge Connectivity
Counting Paths between Vertices
Connectivity (10.4)
 Many problems can be modeled with
paths formed by traveling along the edges
of graphs

 Some examples of such problems are:

Study the link between remote computers in a
netwrok
Efficient planning of routes for mail delivery
Shortest path

40
 Connectivity (Path)
Definition 1:
 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={u=x0,x1}, e2={x1,x2},…, en={xn-1,xn=v}. When the graph is
simple, we denote this path by its vertex sequence x 0, x1, …, xn

 The path is a circuit if it begins and ends at the same vertex,

that is, if u = v.
 A path or circuit is simple if it does not contain the same edge
more than once.
 In in Figure 1,
 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.
 d, e, c, a is not a path, because {e, c} is not an edge
 b, c, f , e, b is a circuit of length 4
 The path a, b, e, d, a, b, which is of length 5, is not
simple because it contains the edge {a, b} twice.

41
 Connectivity (Path)
Definition 2:
 Let n be a nonnegative integer and G a directed graph. A path
of length n from u to v in G is a sequence of n edges e1=(u=x0,x1),
e2=(x1,x2),…, en=(xn-1,xn=v). When When there are no multiple
edges, we denote this path by its vertex sequence x0, x1, …, xn

 The path is a circuit(Cycle) if it begins and ends at the same

vertex, that is, if u = v.
 A path or circuit is simple if it does not contain the same edge
more than once. a
 In the Figure,
b
 a,b,d is a simple path of length 2, c
because (a, b), (b,d) are all edges. d
 d,b,c is not a path, because (d, b) is not
an edge
 c,a,b,c is a Cycle of length 3

42
 Connectivity (10.4)
 Connectedness in undirected graphs

Question asked:
When does a computer network have the
property that every pair of computers can
share information, if message can be sent
through one or more intermediate computers?

This question is equivalent to:

When is there always a path between 2 vertices
in the graph?

43
 Connectivity
Definition 3:
An undirected graph is called connected if there is
a path between every pair of distinct vertices of the
graph. An undirected graph that is not connected
is called disconnected

Example:
G1 is connected while G2 is
Disconnected

Theorem: There is a simple path between every

pair of distinct vertices of a connected undirected
graph
44
Connectivity
A graph that is not connected is the union of
two or more connected subgraphs, each pair
of which has no vertex in common.

These disjoint connected subgraphs are called

the connected components of
the graph

45
How Connected is a Graph?

Suppose that a graph represents a computer

network, and we would also like to understand
how reliable this network is. For instance, will
it still be possible for all computers to
communicate after a router or a
communications link fails?

To answer this and similar questions, we now

develop some new concepts.

46
Cut vertices (Articulation Points) and Cut edges
 A cut vertex (articulation point ) is defined as a vertex
which, when removed along with associated edges,
makes the graph disconnected. i.e., its removal produces
a graph with more connected components

 An articulation point represents a crucial component

in the graph. In a network, it represents an essential
router that cannot fail for all computers to be able to
communicate
b

d
Remove c
a

f e
47
Graph Connectivity
Example: Vertices b, c, and e are cut
a vertices
d off G1. g a d f g

b c e h c e h
G1
Remove vertex b from G1.

a d f g a d f g

b e h b c h
Remove vertex c from G1. Remove vertex e from G1.
 Cut edges
Similarly, cut edge is defined as an edge
which makes the graph disconnected when
removed. i.e., its removal produces a graph
with more connected components
Find the cut edges in G1

{c,e} and {a,b} are cut edges

in G1

a d f g
a d f g

b c e h
Remove edge (a, b) from G1. b c e h
Remove edge (c, e) from G1.
49
VERTEX CONNECTIVITY
Not all graphs have cut vertices. Sometimes we
need to remove more than one vertex to make
the graph disconnected. Consider this graph,
how many vertices you need to remove to make
it disconnected?
1 3
2
4
5

We need to remove at least ______ vertices to

make it disconnected. Next, we will define a
measure of graph connectivity based on the
minimum number of vertices that can be
removed to disconnect a graph. 50
VERTEX CONNECTIVITY
Definition: For every graph G, κ(G) is minimum
number of vertices that can be removed from G
to disconnect it.
We say that a graph is k-connected (or k-
vertex-connected), if κ(G) ≥ k
The larger κ(G) is, the more connected we
consider G to be. Disconnected graphs and K1
have κ(G) = 0
Example:
Remove 1 & 5
 κ(H)=2 3 1 3
H
2 2
4 4
5
51
 Vertex Connectivity (cont’d)
For graph G1, {c} is a vertex
cut. Hence, (G1)=1.

For graph G2, {b, c, f} is a

vertex cut. Hence, (G2)=3.
b b a b c d

c d d h g f e
a a a G2 d

f e f e h g e
G1 Remove vertex c from G1. Remove vertices b, c
and f from G2.
Edge Connectivity
Similarly, Edge connectivity can be defined as:
Definition: The minimum number of edges that
can be removed from G to disconnect it. Denoted
as (G)
If a graph has a cut edge, then (G)=1.
λ(G) = 0 if G is not connected or consists of a
single vertex.
Since it is always possible to disconnect a graph
by removing all edges incident to one of its
vertices, we have:
 0(G)n1. for every3simple graph with n 1vertices! 3
1 Remove
Why?
Example: {1,4} and H 2
Also,
(H)=2 G=K if 2
and only if (G)=n1.
{3,5} Why?
n
4 4
5 5
53
Euler and Hamiltonian
Graphs
Section 10.5
Section Summary
Euler Paths and Circuits
Hierholzer's algorithm (Self-study)
Hamilton Paths and Circuits
Euler and Hamilton Paths (10.5 )
Is it possible to start at some location in the
town, travel across all the bridges once
without crossing any bridge twice and
return to the starting point?

56
Euler Circuit
DEFINITION 1
An Euler circuit in a graph G is a simple circuit
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.

57
Euler Circuit
THEOREM 1
 A connected multigraph with at least two
vertices has an Euler circuit if and only if each
of its vertices has even degree.
Based on the theorem, the
Problem of the town of Konigsberg
has no solution! why?

58
Euler Paths
Definition: An Euler path in a graph G is a simple
path that passes through every edge of the graph
exactly once.
It may revisit vertices, but no edge is repeated.
Theorem: Let G=(V, E) be a connected multigraph,
then we can construct an Euler path in G if and
only if G has exactly two vertices of odd degree.
An Euler path exists if and only if the graph G has
exactly two vertices of odd degree.
Degree of a vertex is the number of edges connected
to it.
Odd degree means the vertex is connected to an odd
number of edges.
Euler Circuits/Paths
Example: Since every vertex in G1 has even degree, G1
has an Euler circuit. (Eulerian graph)
 The Euler circuit: a, b, e, d, c, e, a.

Neither of G2 and G3 has an Euler circuit.

However, G3 has exactly two vertices a and b with odd
degree. Hence, G3 has an Euler path.
The Euler path: a, d, c, a, b, c , e , b. ending vertex
a b a b G3 a b
G1 G2
e e starting vertex

d c d c d c e
deg(a)=2 deg(a)=3 deg(a)=3
deg(b)=2 deg(b)=3 deg(b)=3
deg(c)=2 deg(c)=3 deg(c)=4
deg(d)=2 deg(d)=3 deg(d)=2
deg(e)=4 deg(e)=4 deg(e)=2
 Hierholzer's algorithm for Constructing an Euler Circuit
(Self-study subject)
Requires the graph to have even degree for each vertex.
Basic Idea
1. Start with random vertex x and follow unvisited edges
until returning to x again. You can’t get stuck in a vertex
since when entering another vertex y there must be an
unused edge leaving y (why?) The resulting subcircuit
sub1: x,x1,x2,…,x
2. If the subcircuit covers all edges then you are done.
3. Else, from sub1, choose a starting vertex y with unvisited
edges. Repeat step 1 to construct another subcircuit.
y,y1,y2,…, y. d c
4. Now, patch this circuit onto the first one.
a
x,x1,x2, y,y1,y2,…,y,…,x
You can do this because y is originally in sub 1. e
b
5. Repeat until no more unvisited edges!
 Hierholzer's algorithm (Example)

1. Check for preconditions!(Eulerian

graph) d c

2. Start with g, add f,e,h and return to a f

g
e g
3. Sub1= g,f,e,h,g b
4. e has unvisited edges,start from it h
5. Add a,c,d,a,b, and return to e
6. Sub 2= e,a,c,d,a,b,e
7. Patch sub2 into sub1 at location e:
8. g,f, e,a,c,d,a,b,e,h,g
9. Since all edges are covered, we are
done!
Hierholzer's algorithm for Constructing an Euler Circuit
Input Eulerian graph G
mark all edges, in G, unvisited (black)
start ← pick a random node from G
circuit ← {start}
REPEAT
current = start ← node in circuit with unvisited edge
subcircuit ← {start}
DO
e=(current, u) ← pick unvisited edge incident with
current
mark e visited (red)
subcircuit ← subcircuit ∪ {u}
current ← u
WHILE start ≠ current
Patch subcircuit onto circuit
UNTIL all edges marked visited (red)
output circuit
Dynamics of Hierholzer's algorithm

Start current subcircuit circuit

a a {a} {a} current
current
d {a,d} {a} d c

c {a,d,c} {a}
a {a,d,c,a} {a}
a current
a ∅ {a,d,c,a}
a a {a} {a,d,c,a}
e {a,e} {a,d,c,a} current current
b e
b {a,e,b} {a,d,c,a}
a {a,e,b,a} {a,d,c,a}
{a,e,b,a,d,c,a
a ∅
}
Applications of Euler Paths and Circuits
Euler paths and circuits can be used to solve many
practical problems such as finding a path or circuit
that traverses each
 street in a neighborhood,
 road in a transportation network,
 connection in a utility grid,
 link in a communications network.
Other applications are found in the
 layout of circuits,
 network multicasting,
 molecular biology, where Euler paths are used in the
sequencing of DNA.
Hamilton Paths and Hamilton Circuits
Definition: A simple path in a graph G passes
through every vertex exactly once is called a
Hamilton path.

Definition: A simple circuit in a graph G passes

through every vertex exactly once is called a
Hamilton circuit.

 Example: Graph G1 has a Hamilton circuit a, b, c, d, e, a.

Graph G2 has a Hamilton path a, b, c, d; but not a Hamilton circuit.
Graph G3 has neither a Hamilton path nor a Hamilton circuit.
a b a g
a b b
G1
e c G2 G3
d c c
d e f
d
 Hamilton Paths and Hamilton Circuits (cont’d)
Theorem: (Dirac’s Theorem) If G is a graph with
n vertices, n3, such that the degree of every
vertex is at least n/2 then G has a Hamilton
circuit.
Dirac’s Theorem provide a sufficient condition
for a connected simple graph to have a Hamilton
circuit.
However, it does not provide necessary conditions
for the existence of a Hamilton circuit.
a C5 has a Hamilton circuit, but it does not satisfy
e b Dirac’s Theorem. The best algorithms known for
finding a Hamilton circuit in a graph or determining
no such circuit exists have exponential worse-case
d c complexity in the number of vertices of the graph.
C5
Planar Graph
Section 10.7
Planar Graphs

The famous Utility Graph

Planar Graphs
Definition: A graph is called planar if it can
be drawn in the plane without any edges
crossing.
A crossing of edges is the lines or arcs
representing them at a point other than their
common endpoints.
Such a drawing is called a planar
representation of the graph.

K4 Planar
representation Q3 Planar
of K4 representation
of Q3
Planar Graphs (cont’d)
Example: The graph K3,3 (utility graph) is not
a planar graph.
 In any planar graph v1 and v2 must be connected to
both v4 and v5. These four edges form a closed curve
that splits the plane into two regions R1 and R2.
 Vertex v3 is either in R1 or in R2. If v3 is in R2, then
R2 is separated into two regions, say R21 and R22.
 It is not possible to place vertex v6 without crossing
If vertex v6 is in R1,
an edge. edge {v3, v6}
 Similarly, vertex v3 cannot be in R1.
crosses a line.
v1 v2 v3 v1 v5 v1 v5
v6
v1 v5 R21 R21 v
R1 v3 R1 v6 v 6
3
R22 R 22
R1 R2
v4 v2 v4 v2
If vertex v6 is in If vertex v6 is in R22,
v4 v5 v6 v4 v2
R21, edge {v2, v6} edge {v1, v6}
G
crosses a line. crosses a line.
Euler’s

Formula
Definition: Let G be connected planar simple
graph, G splits the plane into regions, including
an unbounded region.
Theorem: (Euler’s Formula) Let G be a
connected planar simple graph with e edges and
v vertices. Let r be the regions in a planar
representation of G. Then r = e  v + 2.
Corollary: If G is a connected planar simple
graph, then G has a vertex of degree not
exceeding five. R2
r=6
R2 r=2 R6 e=12
r=1 R5 R1 R3
e=1 e=4 v=8
R1 R1 v=4 r=ev+2
v=2 R4
r=ev+2 r=ev+2
Euler’s Formula
Example:
Suppose that a connected planar graph has six
vertices, each of degree four. Into how many
regions is the plane divided by a planar
representation of this graph?
Solution
v=6
e=6*4/2=12 (by handshaking theorem)
Hence, r=e-v+2=12-6+2=8 (by Euler’s formula)