GRAPH THEORY NOTES

3rd Semester, CSE, 2016

Source: Discrete Mathematics and Its Applications by Kenneth H. Rosen (Monmouth University)
Course Instructor: Md. Zaved Iqubal Ahmed

1 Graph Terminologies
• Graphs are discrete structures consisting of vertices and edges that connect these vertices.
• A vertex (singular form of vertices) is any point in a piece of paper with an index associated with it.
• On the other hand, an edge is a line connecting two adjacent vertices.
• There are two broad categories of graphs. They are

1. Directed graph
2. Undirected graph
• Graphs can be used for modelling real world problems and answer questions such as -
1. Can we determine whether it is possible to walk down all streets in a city without going down a street
twice.
2. Can we find the number of colors needed to color the regions of a map.
3. Can we determine whether a circuit be printed on a circuit board.
4. Can a computer, A connected in a network communicate with another computer, B.

1.1 Definition of Graph (Undirected Graph)

A graph G(V, E) consists of V , a non-empty 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.

Undirected Graph Directed graph

1.2 Simple Graph

A graph in which each edge connects two different vertices and where no two edges connect the same pair of vertices.
A Simple graph do not have LOOP and MULTIPLE EDGES.

• LOOP : An edge connecting the same vertex or the edge that connects it self.

• MULTIPLE EDGES: More than one edge between two adjacent vertices.

1
1.3 Multigraph
Graph that may have multiple edges connecting the same vertices are called Multigraph. 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.
That is, we can think of this set of edges as m different copies of an edge {u, v}.

1.4 Pseudograph
Graphs that may include loops, and possibly multiple edges connecting the same pair of vertices or a vertex to itself,
are sometimes called Pseudographs.
Type Edges Multiple Edges Allowed? Loops Allowed?
Simple graph Undirected No No
Multigraph Undirected Yes No
Pseudograph Undirected Yes Yes
Simple directed graph Directed No No
Directed multigraph Directed Yes Yes
Mixed graph Directed and undirected Yes Yes

Simple Graph Multigraph Pseudograph

Directed Graph Directed multigraph Mixed Graph

1.5 Definition of Directed Graph

A directed graph (or digraph) G(V, E) consists of a nonempty set of vertices V and a set of directed edges (or
arcs) E.

• Each directed edge is associated with an ordered pair of vertices.

• The directed edge associated with the ordered pair (u, v) is said to start at u and end at v.

1.6 Directed multigraph

Directed graph that may have multiple directed edges from a vertex to a second (possibly the same) vertex are called
Directed multigraph. 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.

2
1.7 Mixed graph
A graph with both directed and undirected edges as well as with no restriction for loops and multiple edges is called
a Mixed graph. For example, a mixed graph might be used to model a computer network containing links that
operate in both directions and other links that operate only in one direction.

2 Basic terminologies used in Undirected graphs

• Two vertices u and v in an undirected graph G(V, E) are called adjacent (or neighbors) in G(V, E) 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.
• Neighborhood: The set of all neighbors of a vertex v of G(V, E), denoted by N (v), is called the neighbor-
hood of v. If A is a subset of V , we denote by N (A) the set of all vertices in G that are adjacent to at least
one vertex in A. So, N (A) = ∪v∈A N (v).
• Degree: 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).
• A vertex of degree zero is called Isolated vertex.
• A vertex is pendant if and only if it has degree one.

2.1 Theorem: THE HANDSHAKING THEOREM

Let G(V, E) be an undirected graph with m edges. Then
X
2m = deg(v)
v∈V

(Note that this applies even if multiple edges and loops are present.)
. Proof: As an edge is incident on two vertices, we can simply get an insight that an edge, e = {u, v} in a
graph G(V, E) contributes one degree to u and and one degree to v. Therefore, all the edges in a graph contributes
twice in the sum of the degree of all the vertices. Hence, we can say that the sum of the degree of all the vertices in
a graph is twice the number of edges.

2.2 Theorem:
An undirected graph has an even number of vertices of odd degree.
Proof: Degree of a vertex can be either odd or even. Therefore, all the vertices can be partitioned into odd degree
vertex set, Vodd with x elements and even degree vertex set, Veven with y elements. Also,
X X X
deg(v) = deg(v1 ) + deg(v2 ) (1)
v∈V v1 ∈Vodd v2 ∈Veven

X
Since, 2m = deg(v)
v∈V
T heref ore, LHS in eqn(1) is even.
X
Also, deg(v2 ) = sum of y even numbers = even
v2 ∈Veven
X
N ow, in eqn(1), Even = deg(v1 ) + Even
v1 ∈Vodd
X
In order f or eqn(1) be true, deg(v1 ) must be even.
v1 ∈Vodd
Hence proved.

3
3 Basic terminologies used in Directed Graph
• 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.

• [Degree in directed graphs] In a graph with directed edges the in-degree of a vertex v, denoted by 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.)

3.1 Theorem:
Let G(V, E) be a graph with directed edges. Then
X X
deg + (v) = deg − (v) = |E|
v∈V v∈V

4 Special Simple Graphs

4.1 Complete graph
A simple graph that contains exactly one edge between each pair of distinct vertices is a Complete graph.
• A complete graph with n vertices is denoted as Kn .
• The degree of each vertex in Kn is (n − 1).
• A complete graph, Kn has n(n − 1)/2 no. of edges.

4.2 Cycles
A cycle Cn , n ≥ 3, consists of n vertices v1 , v2 , · · · , vn and edges {v1 , v2 }, {v2 , v3 }, · · · , {vn−1 , vn }, and {vn , v1 }.

4
4.3 Wheels
We obtain a wheel Wn when we add an additional vertex to a cycle Cn , for n ≥ 3, and connect this new vertex to

each of the n vertices in Cn , by new edges.

4.4 n-Cubes
An n − dimensional hypercube, or n − cube, denoted by Qn , is a graph that has vertices representing the 2n bit
strings of length n.
⇒ Two vertices are adjacent if and only if the bit strings that they represent differ in exactly one bit position.

4.5 Bipartite graph

A simple graph G(V, E) 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 to a vertex in V2 .
⇒ No edge in G connects either two vertices in V1 or two vertices in V2 .

Examples of Bipartite graphs are given below-

1. Theorem: A simple graph is bipartite if and only if it is possible to assign one of two different colors to
each vertex of the graph so that no two adjacent vertices are assigned the same color.

2. Complete Bipartite Graphs: A complete bipartite graph Km,n is a graph that has its vertex set parti-
tioned into two subsets of m and n vertices, respectively with an edge between two vertices if and only if one
vertex is in the first subset and the other vertex is in the second subset.

3. Matching: Bipartite graphs can be used to model many types of applications that involve matching the
elements of one set to elements of another.
(a) Finding an assignment of jobs to employees can be thought of as finding a matching in the graph model.

5
 (b) A matching M in a simple graph G(V, E) is a subset of the set E of edges of the graph such that no two
edges are incident with the same vertex.
(c) In other words, a matching is a subset of edges such that if {s, t} and {u, v} are distinct edges of the
matching, then s, t, u, and v are distinct.
(d) A vertex that is the endpoint of an edge of a matching M is said to be matched in M .
(e) Maximum Matching: A matching with the largest number of edges.
(f) Complete Matching: We say that a matching M in a bipartite graph G(V, E) with bipartition (V1 , V2 )
is a complete matching from V1 to V2 if every vertex in V1 is the endpoint of an edge in the matching, or
equivalently, if |M | = |V1 |.
(g) HALL’S MARRIAGE THEOREM: The bipartite graph G(V, E) with bipartition (V1 , V2 ) has a
complete matching from V1 to V2 if and only if |N (A)| ≥ |A| for all subsets A of V1 .

5 Subgraphs
Sometimes we need only part of a graph to solve a problem. A part of a graph is nothing but a subgraph of the
given graph.
1. Subgraph: A subgraph of a graph G(V, E) is a graph H(W, F ), where W ⊆ V and F ⊆ E.
2. A subgraph, H of G is a proper subgraph of G if H 6= G.
3. Subgraph induced by a subset W of the vertex set V in a simple graph, G: is the graph K(W, F ),
where the edge set F contains an edge in E if and only if both endpoints of this edge are in W .
4. Removing edges or/and vertices produces subgraphs.
5. On removing a vertex, all the edges incident on the vertex are deleted.
6. Difference between subgraph and subgraph induced by a subset of vertex is shown below-

Graph Any Subgraph Subgraph induced by subset {a, b, c, e}

7. Edge Contraction: In Edge contraction, an edge, e with endpoints u and v is removed and u and v is
merged into a new single vertex w, and for each edge with u or v as an endpoint replaces the edge with one
with w as endpoint in place of u or v and with the same second endpoint.
Hence, the contraction of the edge e with endpoints u and v in the graph G(V, E) produces a new graph
0 0 0 0 0
G (V , E ) (which is not a subgraph of G), where V = V − {u, v} ∪ {w} and E contains the edges in E
which do not have either u or v as endpoints and an edge connecting w to every neighbor of either u or v in V .
8. Union of graphs: The union of two simple graphs G1 (V1 , E1 ) and G2 (V2 , E2 ) is the simple graph with vertex
set V1 ∪ V2 and edge set E1 ∪ E2 . The union of G1 and G2 is denoted by G1 ∪ G2 .

6
6 Graph Representation
We discuss three different ways of representing graphs-

6.1 Adjacency List

1. Adjacency list specify the vertices that are adjacent to each vertex of the graph.

2. Can be used for both direct graphs and undirected graphs.

3. Can represent loops.
4. Cannot represent multiple edges.

5. Best for representing sparse graphs.

6. An example of Adjacency List is shown below-

6.2 Adjacency Matrix

1. Adjacency Matrix is matrix representation of a graph.

2. An adjacency matrix A (or AG ) of G (with n vertices and with listing of the vertices as v1 , v2 , · · · , vn ), is a
n × n zero–one matrix with 1 as its (i, j)th entry when vi and vj are adjacent, and 0 as its (i, j)th entry when
they are not adjacent.
3. Can be used for both direct graphs and undirected graphs.

4. Can represent loops.

5. Can represent multiple edges by using the (i, j)th entry as the number of edges.
6. Best for representing dense graphs.
7. An adjacency matrix of a graph is based on the ordering chosen for the vertices.

8. Hence, there may be as many as n! different adjacency matrices for a graph with n vertices, because there are
n! different orderings of n vertices.
9. The adjacency matrix of a simple graph is symmetric.
10. An example of Adjacency Matrix is shown below-

7
6.3 Incidence Matrix
1. Incidence Matrix is also a matrix representation of a graph.
2. Let G(V, E) be an undirected graph. Suppose that v1 , v2 , ..., vn are the vertices and e1 , e2 , ..., em are the edges
of G. Then the incidence matrix with respect to this ordering of V and E is the n × m matrix M = [mij ],
where (
1 when edge ej is incident with vi ,
mij = (2)
0 otherwise

3. Cannot be used for direct graphs.

4. Can represent loops.

5. Can represent multiple edges by marking each multiple edge.
6. An example of Incidence Matrix is shown below-

7 Isomorphism of graphs
We often need to know whether it is 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? Finding such graphs with same structure is called
Graph Isomorphism.

1. The simple graphs G1 (V1 , E1 ) and G2 (V2 , E2 ) are isomorphic if there exists a one-to-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 in
G2 , for all a and b in V1 . Such a function f is called an isomorphism.
2. Two simple graphs that are not isomorphic are called non-isomorphic.

3. Isomorphism of simple graphs is an equivalence relation.

4. The two graphs G and H below are isomorphic graphs under the mapping f (u1 ) = v1 , f (u2 ) = v4 , f (u3 ) =
v3 , and f (u4 ) = v2 -

5. In the mapping, if ui and uj have an edge then there must be an edge between f (ui ) and f (uj ).

6. Finding isomorphic graphs is very hard.

7. However, finding non-isomorphic graphs is sometimes easy.
8. 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.

9. A property preserved by isomorphism of graphs is called a graph invariant.

8
 10. Some graph invariants -
(a) Isomorphic graphs have same number of vertices and edges.
(b) Isomorphic graphs have same degree for each mapped vertex.
11. If one of the graph invariants is not satisfied, then we can directly tell that the graphs are non-isomorphic.

8 Connectivity
Many problems can be modeled with paths formed by traveling along the edges of graphs. Problems of efficiently
planning routes for mail delivery, garbage pickup, diagnostics in computer networks, and so on can be solved using
models that involve paths in graphs.

8.1 Paths
A path is a sequence of edges that begins at a vertex of a graph and travels from vertex to vertex along edges of the
graph. As the path travels along its edges, it visits the vertices along this path, that is, the endpoints of these edges.

IN UNDIRECTED GRAPHS

• Definition of Path: Let n be a non-negative integer and G an undirected graph. A path of length n from u
to v in G is a sequence of n edges e1 , ..., en of G for which there exists a sequence x0 = u, x1 , ..., xn−1 , xn = v
of vertices such that ei has, for i = 1, ..., n, the endpoints xi−1 and xi .
• When the graph is simple, we denote this path by its vertex sequence x0 , x1 , ..., xn (because listing these vertices
uniquely determines the path).

• Definition of Simple path: A path (Note, first you need to define what is a path) with no repeated edges
is called a Simple path.
• Definition of Circuit: The path (Note, first you need to define what is a path) is a circuit if it begins and
ends at the same vertex, that is, if u = v, and has length greater than zero.

• Definition of Simple circuit: A circuit (Note, first you need to define what is a circuit) with no repeated
edges is called a Simple circuit.

IN DIRECTED GRAPHS

• Definition of Path: Let n be a non-negative integer and G a directed graph. A path of length n from u to
v in G is a sequence of edges e1 , e2 , ..., en of G such that e1 is associated with (x0 , x1 ), e2 is associated with
(x1 , x2 ), and so on, with en associated with (xn−1 , xn ), where x0 = u and xn = v.
• When there are no multiple edges in the directed graph, this path is denoted by its vertex sequence x0 , x1 , x2 , ..., xn .
• Definition of Simple path: When an edge occurs only once, then the path (Note, first you need to define
what is a path) is called a Simple path.

• Definition of Circuit: A path (Note, first you need to define what is a path) of length greater than zero
that begins and ends at the same vertex is called a circuit or cycle.
• Definition of Simple circuit: A circuit (Note, first you need to define what is a circuit) with no repeated
edges is called a Simple circuit.

OTHER TERMINOLOGIES FOR THE PREVIOUS DEFINITIONS

1. WALK: A walk is a sequence of vertices and edges v0 e1 v1 e2 v2 · · · ek , vk such that the edge ei has endpoints
vi−1 and vi ; ∀ 1 ≤ i ≤ k.
2. CLOSED WALK: A walk is a closed walk, if it starts and ends at the same vertex.

9
 3. TRAIL: It is a walk with no repeated edges.
4. CIRCUIT (different from the defined above): It is a closed walk with no repeated edges.
5. PATH (different from the defined above): It is a trail with no repeated vertex.
6. CYCLE: It is a closed trail (circuit) with no repeated vertex other than the first vertex equals to the last
vertex.
Analogy between the different terminologies

Book terminologies Other terminologies

Path Walk
Circuit Closed walk
Simple path Trail
Simple circuit Circuit

9 Connectedness in Undirected Graphs

When does a computer network have the property that every pair of computers can share information, if messages
can be sent through one or more intermediate computers? To answer such questions we need to know how much
connected a graph is.
1. Definition of Connected graphs: An undirected graph is called connected if there is a path between every
pair of distinct vertices of the graph.
2. An undirected graph that is not connected is called disconnected.
3. We disconnect a graph when we remove vertices or edges, or both, and produces a disconnected subgraph.

4. Graph, G1 is connected and graph G2 is disconnected.

10
 5. Theorem: There is a simple path between every pair of distinct vertices of a connected undirected graph.
6. A graph G that is not connected has two or more connected components that are disjoint and have G as their
union.
7. Connected Components: A connected component of a graph G is a connected subgraph of G that is not
a proper subgraph of another connected subgraph of G.
8. Cut vertex: A vertex are called a cut vertex (or articulation point)if its removal from a connected graph
produces a subgraph that is not connected.

9. Cut edge: Cut edge or bridge is an edge whose removal from a connected graph produces a subgraph that
is not connected.

10. Connected graphs without cut vertices are called nonseparable graphs. Example Kn is a non-separable graph.
These graphs can be considered more connected than the graphs with cut vertex. A graph with no cut vertex
or cut edge is given below.

11. Vertex Connectivity

(a) Not all graphs have cut vertex.
(b) Therefore, more no. of vertices need to be removed to disconnect the graph.
0 0
(c) A subset V of the vertex set V of G(V, E) is a vertex cut or separation set, if G − V is disconnected.
(d) Vertex connectivity of a non-complete graph, G, denoted by κ (G), is the minimum number of
vertices in a vertex cut.
(e) When G is a complete graph, it has no vertex cuts, because removing any subset of its vertices and all
incident edges still leaves a complete graph.

11
 (f) Consequently, for every graph G, κ (G) is minimum number of vertices that can be removed from G to
either disconnect G or produce a graph with a single vertex. We have 0 ≤ κ (G) ≤ n − 1 if G has n
vertices.
0
(g) The above graph has a vertex cut, V = {c, f }
(h) The graph,G shown just above has κ (G) = 2.
(i) We say that a graph is k − connected (or k − vertex − connected), if κ (G) ≥ k.
(j) A graph G is 1 − connected if it is connected and not a graph containing a single vertex;
(k) A graph is 2 − connected, or biconnected, if it is nonseparable and has at least three vertices.
(l) Note that if G is a k − connected graph, then G is a j − connected graph for all j with 0 ≤ j ≤ k.

12. Edge Connectivity

(a) Not all graphs have cut edge.
(b) Therefore, if G does not have a cut edge, we look for the smallest set of edges that can be removed to
disconnect it.
0 0
(c) A set of edges E is called an edge cut of G if the subgraph G − E is disconnected.
(d) The edge connectivity of a graph G, denoted by λ (G), is the minimum number of edges in an edge cut
of G.
(e) If G is a graph with n vertices, then 0 ≤ λ (G) ≤ n − 1.
0
(f) The above graph has a edge cut, E = {{b, c}, {g, f }, {a, f }}
(g) The graph,G shown just above has λ (G) = 3.
13. The inequality for vertex connectivity and edge connectivity is

κ (G) ≤ λ (G) ≤ min deg(v)

v∈V

10 Connectedness in Directed Graphs

1. A directed graph is strongly connected if there is a path from a to b and from b to a whenever a and b are
vertices in the graph.
2. A directed graph is weakly connected if there is a path between every two vertices in the underlying undirected
graph.
3. The subgraphs of a directed graph, G that are strongly connected but not contained in larger strongly connected
subgraphs, that is, the maximal strongly connected subgraphs, are called the strongly connected components
or strong components of G.
4. A strongly connected graph is always a weakly connected graph. But a weakly connected graph is not
necessarily a strongly connected graph.
5. Graph, G is strongly connected as well as weakly connected. However, graph H is weakly connected.

12
11 Euler Path and Circuit
1. An Euler circuit in a graph G is a simple circuit containing every edge of G.
2. An Euler path in G is a simple path containing every edge of G.
3. All Euler circuits are euler paths, but all Euler paths are not Euler circuits.

4. The graph G1 has an Euler circuit, Ex. a, e, c, d, e, b, a. Also, an Euler path.

5. Graphs G2 has neither Euler circuit nor Euler path.
6. Graph G3 has no Euler circuit but has an Euler path, namely, a, c, d, e, b, d, a, b.

7. Graph H1 has no Euler path and Euler circuit.

8. The graph H2 has an Euler circuit, Ex., a, g, c, b, g, e, d, f, a. Also, an Euler path.
9. H3 has no Euler circuit but has an Euler path, namely, c, a, b, c, d, b,.

10. Theorem: A connected multigraph with at least two vertices has an Euler circuit if and only if each of its
vertices has even degree.
11. Theorem: A connected multigraph has an Euler path but not an Euler circuit if and only if it has exactly
two vertices of odd degree.
12. Following is Fleury’s Algorithm for printing Euler path or Euler circuit (source geeks4geeks).

(a) Make sure the graph has either 0 or 2 odd vertices.

(b) If there are 0 odd vertices (condition for existence of Euler circuit), start anywhere. If there are 2 odd
vertices (condition for existence of Euler path), start at one of them.
(c) Follow unmarked edges one at a time. And mark it. If you have a choice between a bridge and a non-bridge,
always choose the non-bridge.
(d) Stop when you run out of unmarked edges.
(e) If you end at the start vertex, it is an Euler circuit. And if you end at an odd degree vertex, it is an Euler
path.
13. Application: Many applications ask for a path or circuit that traverses each street in a neighborhood, each
road in a transportation network, each connection in a utility grid, or each link in a communications network
exactly once. Finding an Euler path or circuit in the appropriate graph model can solve such problems.

12 Hamilton Path and Circuit

1. A simple path in a graph G that passes through every vertex exactly once is called a Hamilton path.

13
 2. A simple circuit in a graph G that passes through every vertex exactly once is called a Hamilton circuit.

3. Graph G1 has a Hamilton circuit: a, b, c, d, e, a. Therefore, it also has a Hamilton path.

4. There is no Hamilton circuit in G2 but G2 does have a Hamilton path, namely, a, b, c, d.
5. G3 has neither a Hamilton circuit nor a Hamilton path.

6. The best algorithms known for finding a Hamilton circuit in a graph or determining that no such circuit exists
have exponential worst-case time complexity.
7. There are no known simple necessary and sufficient criteria for the existence of Hamilton circuits.
8. However, many theorems are known that give sufficient conditions for the existence of Hamilton circuits.

9. 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.
10. 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 circuit.
11. Both Ore’s theorem and Dirac’s theorem provide sufficient conditions for a connected simple graph to have a
Hamilton circuit.
12. However, these theorems do not provide necessary conditions for the existence of a Hamilton circuit. For
example, the graph C5 has a Hamilton circuit but does not satisfy the hypotheses of either Ore’s theorem or
Dirac’s theorem, as the reader can verify.

13. Also, certain properties can be used to show that a graph has no Hamilton circuit. Some of them are -
(a) A graph with a vertex of degree one cannot have a Hamilton circuit, because in a Hamilton circuit, each
vertex is incident with two edges in the circuit.
(b) If a vertex in the graph has degree two, then both edges that are incident with this vertex must be part
of any Hamilton circuit.
(c) A Hamilton circuit cannot contain a smaller circuit within it.
14. Kn has a Hamilton circuit whenever n ≥ 3.
15. Application: The famous traveling salesperson problem or TSP (also known in older literature as the
traveling salesman problem) asks for the shortest route a traveling salesperson should take to visit a set of
cities. This problem reduces to finding a Hamilton circuit in a complete graph such that the total weight of its
edges is as small as possible.

13 Planner Graphs
1. A graph is called planar if it can be drawn in the plane without any edges crossing (where a crossing of edges
is the intersection of the lines or arcs representing them at a point other than their common endpoint).
2. Such a drawing is called a planar representation of the graph.

14
 3. A graph may be planar even if it is usually drawn with crossings, because it may be possible to draw it in a
different way without crossings.
4. Examples of planner graphs: K4 , Q3 , Cn , Wn , etc.
5. Examples of Non-planner graphs: K3,3 , K5 , etc.

6. A planar representation of a graph splits the plane into regions, including an unbounded region.
7. The planar representation of the graph below splits the plane into 6 regions.

8. EU LER0 S F ORM U LA : 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.

9. COROLLARY 1 : If G is a connected planar simple graph with e edges and v vertices, where v ≥ 3, then
e ≤ 3v − 6.
10. COROLLARY 2 : If G is a connected planar simple graph, then G has a vertex of degree not exceeding five.
11. 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.
12. We have seen that K3,3 and K5 are not planar. Clearly, a graph is not planar if it contains either of these two
graphs as a subgraph.
13. If a graph is planar, so will be 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.
14. 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.

15. The subgraph, H of graph, G is homeomorphic to K5 . Therefore, the graph, G is non-planner.

16. Kuratowski’s Theorem: A graph is nonplanar if and only if it contains a subgraph homeomorphic to K3,3
or K5 .

17. Application: Planarity of graphs plays an important role in the design of electronic circuits. We can model
a circuit with a graph by representing components of the circuit by vertices and connections between them
by edges. We can print a circuit on a single board with no connections crossing if the graph representing the
circuit is planar. When this graph is not planar, we must turn to more expensive options.

15
14 Graph Coloring
1. Problems related to the coloring of maps of regions, such as maps of parts of the world, have generated many
results in graph theory.
2. When a map is colored, two regions with a common border are customarily assigned different colors.
3. Each map in the plane can be represented by a graph. To set up this correspondence, each region of the map
is represented by a vertex.
4. Edges connect two vertices if the regions represented by these vertices have a common border. Two regions
that touch at only one point are not considered adjacent.
5. The resulting graph is called the dual graph of the map.

6. It is clear that any map in the plane has a planar dual graph.

7. The problem of coloring the regions of a map is equivalent to the problem of coloring the vertices of the dual
graph so that no two adjacent vertices in this graph have the same color.
8. 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.
9. Chromatic Number: The chromatic number of a graph is the least number of colors needed for a coloring
of this graph.
10. The chromatic number of a graph G is denoted by χ(G).
11. THE FOUR COLOR THEOREM: The chromatic number of a planar graph is no greater than four.
12. Chromatic number of:

(a) Kn is n
(b) Bipartite graph is 2
(c) Cn is 3 if n is odd and 2 if n is even.
13. Application: Graph coloring has a variety of applications to problems involving scheduling and assignments.

***BEST OF LUCK***

***If you are caught with this in the exam, your paper will be cancelled***

16