CHAPTER – 1

1.1 Introduction
1.1.1 HISTORY OF GRAPH THEORY
The study of graphs, also known as graph theory,, is an important part of many
disciplines, including mathematics, engineering, physical, social, biological, and computer
science, linguistics, and many others. The history of graph theory can be traced back to 1735,
when Leonhard Euler, a Swiss mathematician, solved the Konigsberg bridge problem.
problem

A graph is collection of pints known as nodes or vertices that are linked together by a
network of lines known
wn as edges. Because graph theory is considered a branch of applied
mathematics, it is no surprise that graph theory has been independently discovered numerous
times.

1.1.2 WHO INVENTED GRAPH THEORY

In 1736, Euler (1707-1782)
1782) published a paper in which he solved the Konigsberg bridge
problem, which gave birth to graph theory. Because graph theory is thought to have begun in
1736 with the publication of Euler’s solution to the Konigsberg bridge probl
problem
em, Euler became
known as the “Father
Father of Graph Theory
Theory.”

Nothing more was done in this field for the next 100 years.
 Then, in 1847, G.R. Kirchhoff (1824
(1824-1887) developed d the tree theory in electrical
networks for their applications. Kirchhoff’s research into electric networks led to the
development of the fundamental concepts and theorems relating to trees in graphs.
 area. Thousands o0f papers and more than a dozen books have been published in the
last decade.

 There have already been a great many rediscoveries of graph theory, in the twenty-first
century.

1.2 GRAPHS
Definition 1.2.1
A graph is a non-linear kind of data structure made up of nodes or vertices and edges.
The edges connect any two nodes in the graph, and the nodes are also known as vertices. This
graph has a set of vertices V= { 1,2,3,4,5} and a set of edges E= {
(1,2),(1,3),(2,3),(2,4),(2,5),(3,5),(4,5) }.

Definition 1.2.2
In graph theory, the degree of a vertex is the number of edges connecting it. In the
example below, vertex a has degree 5 , and the rest have degree 1 . A vertex with degree 1 is
called an "end vertex" (you can see why).

Definition 1.2.3
A loop is an edge that connects a vertex to itself. If a graph has more than one edge
joining some pair of vertices then these edges are called multiple edges. Simple Graph. A
simple graph is a graph that does not have more than one edge between any two vertices and
no edge starts and ends at the same vertex.

Definition 1.2.4
• Vertices u, v are adjacent in G if (u, v) ∈ E(G).
  If all the 4 conditions satisfy, even then it can’t be said that the graphs are surely
isomorphic.
 However, if any condition violates, then it can be said that the graphs are surely not
isomorphic

Sufficient Conditions 1.3.3

The following conditions are the sufficient conditions to prove any two graphs
isomorphic.
If any one of these conditions satisfy, then it can be said that the graphs are surely
isomorphic.

 Two graphs are isomorphic if and only if their complement graphs are isomorphic.
 Two graphs are isomorphic if their adjacency matrices are same.
 Two graphs are isomorphic if their corresponding sub-graphs obtained by deleting
some vertices of one graph and their corresponding images in the other graph are
isomorphic.

Problem
Practice problems based on graph isomorphism.

Are the following two graphs isomorphic?

G1 G2

Checking Necessary Conditions.

Condition-01:
 Number of vertices in graph G1 = 4

 Number of vertices in graph G2 = 4

Here,
  Both the graphs G1 and G2 have same number of vertices.
 So, Condition-01
01 satisfies.

Condition-02:
 Number of edges in graph G1 = 5
 Number of edges in graph G2 = 6
Here,
 Both the graphs G1 and G2 have different number of edges.
 So, Condition-02
02 violates.

Since Condition-02
02 violates, so given graphs can not be isomorphic.
∴ G1 and G2 are not isomorphic graphs
graphs.

1.4 The adjacency and incidence matrices

Let [n] = {1,...,n}.

Definition 1.4.1
Let G = (V,E) be a graph with V = [n]. The adjacency matrix A = A(G)) is the n×n
symmetric matrix defined by
 Example

Remark 1.4.2
Any adjacency matrix A is real and symmetric, hence the spectral theorem proves that
A has an orthogonal basis of eigenvalues with real eigenvectors. This important fact allows us to
use spectral methods
ods in graph theory. Indeed, there is a large sub
subfield
field of graph theory called
spectral graph theory.

Definition 1.4.3.

Let G = (V,E) be a graph with V = {v1,...,vn} and E = {e1,...,em}. Then the

incidence matrix B = B(G) of G is the n×m matrix de
defined by

Example

Remark 1.4.4.
Every column of B has |e| = 2 entries 1.
1.5 Degree
It is the number of vertices adjacent to a vertex V.
Notation − deg(V).
In a simple graph with n number of vertices, the degree of any vertices is −
deg(v) = n – 1 ∀ v ∈ G
A vertex can form an edge with all other vertices except by itself. So the degree of a
vertex will be up to the number of vertices in the graph minus 1. This 1 is for the self-vertex
as it cannot form a loop by itself. If there is a loop at any of the vertices, then it is not a Simple
Graph.
Degree of vertex can be considered under two cases of graphs −

 Undirected Graph
 Directed Graph

Degree of Vertex in an Undirected Graph

An undirected graph has no directed edges. Consider the following examples.

Example 1
Take a look at the following graph −

In the above Undirected Graph,

 deg(a) = 2, as there are 2 edges meeting at vertex 'a'.
 deg(b) = 3, as there are 3 edges meeting at vertex 'b'.
 deg(c) = 1, as there is 1 edge formed at vertex 'c'
So 'c' is a pendent vertex.
 deg(d) = 2, as there are 2 edges meeting at vertex 'd'.
 deg(e) = 0, as there are 0 edges formed at vertex 'e'.
 So 'e' is an isolated vertex
vertex.

1.6 Subgraphs
Definition 1.6.1
A Subgraph S of a graph G is a graph whose vertex set V(S) is a subset of the vertex set V(G),
that is V(S)⊆V(G), and whose edge set E(S) is a subset of the edge set E(G), that is E(S)⊆E(G)
E .

Essentially, a subgraph is a graph within a larger graph. For example, the following graph S is a
subgraph of G

Example

1.7 Special graphs

 Kn is the complete graph, or a clique. Take n vertices and all possible edges connecting
them.

 An empty graph has no edges.

 G = (V,E) is bipartite if there is a partition V = V1 ∪V2 into two disjoint sets such that
each e ∈ E(G) intersects both V1 and V2.

 Kn,m is the complete bipartite graph. Take n + m vertices partitioned into a set A of size
n and a set B off size m, and include every possible edge between A and B.

Example.
1.8 Walks, paths and cycles
Definition 1.8.1
A walk in G is a sequence of vertices v0,v1,v2,...,vk, and a sequence of edges (vi,vi+1) ∈
E(G). A walk is a path if all vi are distinct. If for such a path w
with k ≥ 2, (v0,vk) is also an edge in
G, then v0,v1,...,vk,v0 is a cycle. For multigraphs, we also consider loops and pairs of multiple
edges to be cycles.

Definition 1.8.2
The length of a path, cycle or walk is the number of edges in it.

Example.

Proposition 1.8.3

Every walk from u to v in G contains a path between u and v.

Proof.
By induction on the length l of the walk u = u0,u1,...,vl = v.
If l = 1 then our walk is also a path. Otherwise, if our walk is not a path there is ui = uj with i < j,
then u = u0,...,ui,uj+1,...,v is also a walk from u to v which is shorter. We can use induction to
conclude the proof.
Proposition 1.8.4

Every G with minimum degree δ ≥ 2 contains a path of length δ and a cycle of

length at least δ + 1.

Proof.

Let v1,...,vk be a longest path in G. Then all neighbours of vk belong to v1,...,vk−1

v1,...,vk so
k−1 ≥ δ and k ≥ δ + 1, and our path has at least δ edges. Let i (1 ≤ i ≤ k−1)
−1) be the minimum
index such that (vi,vk) ∈ E(G). Then the neighbours of vk are among vi,...,vk−1,
vi,...,vk so k −i ≥ δ.
Then vi,vi+1,...,vk is a cycle of length at least δ + 1.

Remark 1.33.
Note that
hat we have also proved that a graph with minimum degree δ ≥ 2 contains cycles
of at least δ−1
−1 different lengths. This fact, and the statement of Proposition 1.32, are both tight;
to see this, consider the complete graph G = Kδ+1.
Chapter 1
Graphs
Graphs isomorphism
The adjacency and incidence matrices
Degree
Sub graphs
Special graphs
Walks, path and cycles
Connectivity
Chapter 2
Operations on graphs
Union of graphs
Addition of graphs
Multiplication on graphs
Line graphs
Closure of graphs
Chapter 3
Trees
Equivalent definitions of trees
Cayley’s formula
Chapter 4
Connectivity in graphs
Vertex connectivity
Edge connectivity
Blocks
2-connected graphs
Mergers theorem
Chapter 5
Problems on connectivity
GRAPHS

Definition 1.1. A graph is a non-linear kind of data structure made up of nodes or vertices
and edges. The edges connect any two nodes in the graph, and the nodes are also known as
vertices. This graph has a set of vertices V= { 1,2,3,4,5} and a set of edges E= {
(1,2),(1,3),(2,3),(2,4),(2,5),(3,5),(4,5) }.

Definition 1.2. In graph theory, the degree of a vertex is the number of edges connecting it.
In the example below, vertex a has degree 5 , and the rest have degree 1 . A vertex with degree
1 is called an "end vertex" (you can see why).