Unit - 4
Graph terminology
Overview:
Graph theory is intimately related to many branches of mathematics. It is widely applied in subjects like, Computer Technology, Communication Science, Electrical Engineering, Physics, Architecture, Operations Research, Economics, Sociology, Genetics, etc. In the earlier stages it was called slum Topology. It also has uses in social sciences, chemical sciences, information retrieval systems, linguistics even in economics also.
Graphs are discrete structures consisting of vertices and edges that connects these vertices. There are several different types of graphs that differ with respect to the kind and number of edges that can a connect a pair of vertices. Problems in almost every conceivable discipline can be solved using graph models.
Basic terminology-
Graph theory is a relatively new area of mathematics
Graph is the form of representing of descriptive data in the terms of verticals and edges.
Graph theory is used in various fields like computer science, information technology, genetics, telecommunication etc.
A graph is a collection of vertices and edges in which each edge is assigned to pair of points called terminal.
We can say that a graph is a network of dots connected by lines.
Mathematically we can define a graph as-
A graph is a pair of set (V, E) where-
1. V is a non-empty set whose elements are called vertices.
2. E is collection of two-element subset of V called edges.
Terminology: A graph G is an ordered pair (V, E) where V is a non-empty set and E is the set of edges in which each element of E is assigned to a unique unordered pair of elements of V.
An element of a set E is generally denoted as- e = (v,u) where u, v ∈ V.
U and v are called the end vertices of edge e.
Note- In any graph the number of vertices with odd degree must be even.
Loop: If both the end vertices of an edge are same then the edge is called a loop.
Parallel edge: If two or more edges have same terminal vertices, then these edges are called parallel edges.
Example: Consider the graphs given below-
Check whether these graphs are same or not?
Sol.
As we can see that these graphs are not same because here 
and 
are not same since 
but a does not belongs to 
.
These two graphs look same but not equal.
We can draw these graphs as below-
These types of graphs are known as isomorphic graph when they are same except for the name of vertices.
Simple graph: A graph which has no loops and parallel edges is known as simple graph.
Compound graph: A graph which contains loops or parallel edges is called compound or multi-graph.
Degree of vertex: The number of edges incident on a vertex v is called degree of vertex v, with loop being counted twice.
We can denote it as-
Degree of v = d(v)
Examples of graph and multi-graph are-
Graph-
Multi-graph-
Weighted Graphs
A graph G is said to be a weighted graph if each edge e of G is assigned a non-negative number w(e) called the weight of v.
The weighted graph is given below-
Sub Graphs-
We can say that 
is a sub-graph of G = (V, E), and write 
provided 
.
We can say that 
is an induced sub-graph of G = (V, E), provided 
and every edge in E whose vertices are still in 
is also an edge in 
.
Isomorphic graphs-
Let 
and 
be two graphs. The graph 
and 
are said to be isomorphic if there is a bijective function 
such that if u and v are end vertices of some edge e ∈ 
then 
end vertices of 
Or in other words,
Two graphs G1 and G2 are said to be isomorphic if −
- Their number of components (vertices and edges) are same.
- Their edge connectivity is retained.
Note − In short, out of the two isomorphic graphs, one is a tweaked version of the other. An unlabelled graph also can be thought of as an isomorphic graph.
There exists a function ‘f’ from vertices of G1 to vertices of G2
[f: V(G1) ⇒ V(G2)], such that
Case (i): f is a bijection (both one-one and onto)
Case (ii): f preserves adjacency of vertices, i.e., if the edge {U, V} ∈ G1, then the edge {f(U), f(V)} ∈ G2, then G1 ≡ G2.
Note
If G1 ≡ G2 then −
|V(G1)| = |V(G2)|
|E(G1)| = |E(G2)|
Degree sequences of G1 and G2 are same.
If the vertices {V1, V2, .. Vk} form a cycle of length K in G1, then the vertices {f(V1), f(V2),… f(Vk)} should form a cycle of length K in G2.
All the above conditions are necessary for the graphs G1 and G2 to be isomorphic, but not sufficient to prove that the graphs are isomorphic.
- (G1 ≡ G2) if and only if (G1− ≡ G2−) where G1 and G2 are simple graphs.
- (G1 ≡ G2) if the adjacency matrices of G1 and G2 are same.
- (G1 ≡ G2) if and only if the corresponding subgraphs of G1 and G2 (obtained by deleting some vertices in G1 and their images in graph G2) are isomorphic.
Example
Which of the following graphs are isomorphic?
In the graph G3, vertex ‘w’ has only degree 3, whereas all the other graph vertices has degree 2.
Hence G3 not isomorphic to G1 or G2.
Taking complements of G1 and G2, you have −
Here, (G1− ≡ G2−), hence (G1 ≡ G2).
Complete Graphs-
A simple graph G is called a complete graph, if there is an edge between each pair of vertices.
Regular Graphs-
If all vertices of a graph G have same degree, then G is called as a regular graph.
Bipartite Graphs-
A graph G(V, E) is said to be bipartite, if the vertex set V can be partitioned in to two non-empty disjoint subset 
and 
such that each edge is G had end vertex is 
and other end vertex in 
There is no edge between two vertices of 
as well as there is no edge between two vertices of 
.
Here 
bipartition of V.
Applications of graph theory-
Applications in computer Science
In computer science graph theory is used for the study of algorithms like:
Dijkstra's Algorithm
Prims's Algorithm
Kruskal's Algorithm
1. Graphs are used to define the flow of computation.
2. Graphs are used to represent networks of communication.
3. Graphs are used to represent data organization.
4. Graph transformation systems work on rule-based in-memory manipulation of graphs. Graph databases ensure transaction-safe, persistent storing and querying of graph structured data.
5. Graph theory is used to find shortest path in road or a network.
6. In Google Maps, various locations are represented as vertices or nodes and the roads are represented as edges and graph theory is used to find the shortest path between two nodes.
Sub-graphs:
Def: Let G and H be two graphs. H is called a subgraph of G if V (H) is a subset of V (G) and E (H) is a subset of E (G).
If H is a subgraph of G then
(i) All the vertices of H are in G.
(ii) All the edges of H are in G.
(iii) Each edge of H has the same end points in H as in G.
For example:
In Fig. Given below H is a subgraph of G.
Isomorphism of graphs: Two graphs are said to be isomorphic it they have identical behaviour in terms of graph-theoretic properties. More precisely:
Let Let G1 (V1, E1) and G2 (V2, E2) be two simple undirected graphs. A function f: V1 
V2 is called a graph isomorphism if i) f is one-one and onto, i.e there exists a one-to-one correspondence between their vertices as well as edges (both the graphs have equal number of vertices and edges, however, vertices may have different levels.)
Ii) for all u,vV1, {u,v} E1 if and only if {f(u), f(v)} E2
If such a function exists, then the graphs G1 and G2 are called isomorphic graphs.
Example: Verify that the graphs given below are isomorphic.
Sol:
The correspondence between the two graphs is as follows: The vertices 1, 2, 3 and 4 in G is corresponds to v1, v4, v3 and v2 respectively in
H. The edges a, b, c, d in G corresponds to e1, e3, e2, e4 respectively.
Note : i) Two isomorphic graphs have equal number of vertices and edges.
Ii) Two isomorphic graphs have equal number of vertices with same degree.
Example: Show that the graph displayed below are not isomorphic.
Sol:
The graph G and H both have five vertices and six edges. However the graph H has a vertex of degree one namely v3. Where as G has no vertices of egree one. Hence G and H are not isomorphic.
Example: Show that the simple graphs with the following adjacency matrices are isomorphic.
Sol:
Since the given adjacency matrices are of order three each, so its graph has three vertices namely v1, v2, v3 and u1, u2, u3 respectivety.
There is a one-to-one correspondence between the vertices and edges of the graph G and H. Both the graph has there vertices and 3 edges each. Two vertices of the graph G has degree one and one vertex has degree two. Again two vertices of the graph H has degree one and one vertex has degree two. The vertices v1, v2 and v3 in G corresponds to u2, u3 and u1 in H respectively. The edges e1 and e2 in G corresponds to 1 and 2 in H respectively.
Hence both the graph are isomorphic.
Connectivity of a graph:
Walk: A walk is defined as a finite alternating sequence of vertices and edges, beginning and ending with vertices, such that each edge is incident with the vertices preceding and following it. Let u, v be any two vertices in an undirected graph G. Then a walk u-v in G is finite alternating sequence u-v1 e1 v2 e2 ... ... ... En vn = V of vertices and edges. Vertices with which a walk begins and ends are called terminal vertices.
Open and closed walk: A walk is said to be closed walk if it is possible that a walk begins and end at the same vertex.
A walk that is not closed is called an open walk.
Path: An open walk in which no vertex appears more than once is called a path. The number of edges in a path is called the length of the path.
An edge which is not a loop is s path of length one. A loop can be included in a walk but not in a path.
Circuits: A circuit is a closed walk of non-zero length that contains no repeated edges except the initial and end vertex where initial and end vertex. That is, a circuit is a closed, non-intersecting walk. A circuit is also called elementary cycle, circular path and polygon.
In figure above, examples of walk, path and circuits are given bellow.
Walk: v1 e1 v2 e2 v3 e3 v3 e4 v4 etc
Path: v1 e1 v2 e2 v3 e4 v4 etc
Circuit: v2 e1 v3 e4 v9 e5 v5 e6 v2 etc
Connected graphs: A graph is said to be connected if we can reach any vertex from any other vertex by traveling along the edges. More formally: A graph is said to be connected if there exists at least one path between every pair of its vertices, otherwise, the graph is disconnected.
That is a graph G is connected if give any vertices u and v, it is possible to travel from u to v along a sequence of adjacent edges fig. Given above is connected
Graph but in fig. Above is a disconnected graph.
Cut points and Bridges: Vertex v in a connected graph G is called a cutpoint if G-v is disconnected, where G-v is the graph obtained from G by deleting the vertex v and all the edges connecting v. In fig, vertex v4 is the cutpoint
An edge e of a connected graph G is called a bridge or cut edge if Ge is disconnected. In fig. Below, the edge (v4, v5) is a bridge.
We can represent a graph in matrix form in two ways-
1. Adjacent matrix
2. Incidence matrix
Adjacency matrix of a non-directed graph-
Let G be a graph with n vertices and no parallel edges. The adjacency matrix of G in a n × n. Symmetric binary matrix A (G) = [aij]n n
Where
Where 
and 
are vertices of G.
The following is a example of the adjacency matrix of the simple graph G.
Adjacency matrix x; A (G)-
Adjacency matrix of a Digraph-
Let G be a digraph with n vertices, containing non-parallel edges. The adjacency matrix A(G) of the digraph G is an n × n matrix defined by
A(G) = [aij]nn
= 0 otherwise
Example: Find the adjacency matrix of the graph-
Sol. The adjacency matrix of the above graph will be-
Incidence matrix of a non-directed graph-
Let G be a graph with n vertices and m edges. The incidence matrix denoted by X (G) is defined as the matrix X (G) is defined as the matrix
X(G) = [xij]nn
= 0, otherwise
X (G) is an n by m matrix whose n rows correspond to the n vertices, and mcolumns correspond to m edges.
Graph and its incidence matrix-
Paths-
Let G be a non-directed graph. A sequence P of zero or more edges of the form 
, where 
are the vertices of G is called a path in G.
We denote this by P
The vertex 
is called the initial vertex and the vertex 
is called the terminal vertex of the path P.
Cycle- A cycle is a circuit in which no vertex except the first (which is also the last) appears more than once.
An n-cycle is a cycle with nn vertices.
The set of vertices and edges which go to make up a cycle form a subgraph.
This subgraph itself is also referred to as a cycle.
Odd Cycle
An odd cycle is a cycle with odd length, that is, with an odd number of edges.
Even Cycle
An even cycle is a cycle with even length, that is, with an even number of edges.
Note-
1. If
then the path P is called an open path and if 
then the path is called closed path.
2. If all the edges and vertices in a path P are distinct except possibly the end points then the path P is called a simple path.
Connectivity of a graph:
Edge connectivity: Each cut-set of a connected graph G consists of a certain number of edges. The number of edges in the smallest cut-set (i,e cut-set with fewest number of edges) is defined as the edge connectivity of G.
Equivalently the edge connectivity 
(G) of a connected graph can be defined as the minimum number of edges whose removal reduces the graph disconnected. If G is a tree, then 
(G) = 1, became removel of any one edges reduces the the tree disconnected.
(G) = 2
Vertex connectivity: The vertex connectivity K(G) of a connected graph G is defined as the minimum number of vertices whose removal from G leaves the graph disconnected. If G is a tree then K(G) = 1
Eulerian graph:
A undirected graph with no isolated vertices is said to have an Euler circuit if there is a circuit in G that traverses every edge of the graph exactly once. If there is an open trail from vertex u to v in G and this trail traverses each edge in G exactly once, the trail is called Euler trail. [A trail from a vertex u to v is a path that doesnot involve a repeated edge] An Eulerian tour is a closed walk that starts at some vertex, passes through each edge exactly once and returns to the starting vertex.
Since any closed walk in an undirected graph enters and leaves any vertex the same number of times, the subgraph composed of the edges in any closed walk is even. Thus, if the graph contains a closed walk passing through each edge exactly once, the graph must be even, conversely, if the graph is even, then it contains an Euler tour, A path that passes through each edge exactly once but vertices may be repeated is called Euler path. A graph that contains an Euler tour or Euler circuit is called an Eulerian graph.
Note: i) If a graph G has a vertex of odd degree, then there can be no Euler circuit in G.
Ii) if a graph G is connected and each vertex has even degree, then there is an Euler circuit.
For example the graph in fig below in an Eulerian graph because all the vertices are of even degree, so it has an Eulerian circuit
v1
v2
v3
v5
v4
v3
v1
But the graph G in fig. Given below is not a Eulerian graph because all the vertices of G are not even degrees, so there does not have any Euler circuit.
Hamiltonian graph: Let G be a connected graph with more than two vertices. If there is a path in G that uses each vertex of the graph exactly once, then such a path is called Hamiltonian path. If the path is a circuit that contains each vertex in G exactly once, except the initial vertex, then such a path is called a Hamiltonian circuit.
A graph that contains a Hamiltonian circuit is called a Hamiltonian graph.
Note: i) The complete bipartite graph km, n is Hamiltonian if m = n and m>1.
Ii) Eulerian circuit uses every edge exactly once but many repeat vertices, while Hamiltonian circuit uses each vertex exactly once except for the first and last vertex.
Example: Draw three graph which are
i) Hamiltonian but not a Eulerian
Ii) Neither Eulerian nor Hamiltonian
- Hamiltonian but not a Eulerian
2. Neither Eulerian nor Hamiltonian
Here we will discuss about graphs which can be drawn on a plane such that no two edges of the graph intersect. The points of intersection of edges in a graph are called cross-overs. The edges in a graph G, which intersect are said to cross-over each other. A graph G is said to be embedded in a surface
S, when it can be drawn on S, such that no two edges intersect.
Now let’s define the planar graph- A graph G is said to be planar if it can be drawn on a plane without cross-overs.
Or in other words, When a connected graph can be drawn without any edges crossing, it is called planar.
When a planar graph is drawn in this way it divides the plane into region called faces.
The following graph is a planar graph-
We can draw it like this-
It is clear that a graph is planar if it can be embedded in a plane. A graph which cannot be drawn a plane without cross-over between its edges is called non-planar graph.
Plane graph
An embedding of a planar graph is called a plane graph.
A plane graph partitions the plane into several regions. These are called faces (also called windows or meshes). Each region is characterized by the set of edges forming its boundary. Each plane graph determines a region of infinite area called the exterior region of G. If G is a connected graph, then the boundary of a region R is a closed path in which each cut edge is travelled twice. The boundary of a region R is a cycle if the boundary of R contains no cut edges of G.
Degree of a face:
Let G be a plane graph and f be a face of G. The degree of the face f is defined as the number of edges in the boundary of f, with cut edges counted twice.
Critical planar graph:
A graph G is said to be critical planar if G is non-planar but any sub-graph obtained by removing a vertex of G is planar.
Euler’s formula for planar graph-
For any planar graph with v vertices, e edges and f faces, we have-
Example
Regions
Every planar graph divides the plane into connected areas called regions.
Example 1:
Solution: Degree of a bounded region r = deg(r) = Number of edges enclosing the regions r.
Deg(1)=3
Deg(2)=4
Deg(3)=4
Deg(4)=3
Deg(5)=8
Example 2:
Solution: Degree of an unbounded region r = deg(r) = Number of edges enclosing the regions r.
Deg(
Deg(
In planar graphs, the following properties hold good −
- 1. In a planar graph with 'n' vertices, sum of degrees of all the vertices is
n ∑ i=1 deg(Vi) = 2|E|
- 2. According to Sum of Degrees of Regions Theorem, in a planar graph with 'n' regions, Sum of degrees of regions is −
n ∑ i=1 deg(ri) = 2|E|
Based on the above theorem, you can draw the following conclusions −
In a planar graph,
- If degree of each region is K, then the sum of degrees of regions is
K|R| = 2|E|
- If the degree of each region is at least K(≥ K), then
K|R| ≤ 2|E|
- If the degree of each region is at most K(≤ K), then
K|R| ≥ 2|E|
Note− Assume that all the regions have same degree.
3. According to Euler's Formulae on planar graphs,
- If a graph 'G' is a connected planar, then
|V| + |R| = |E| + 2
- If a planar graph with 'K' components then
|V| + |R|=|E| + (K+1)
Where, |V| is the number of vertices, |E| is the number of edges, and |R| is the number of regions.
4. Edge Vertex Inequality
If 'G' is a connected planar graph with degree of each region at least 'K' then,
|E| ≤ 
- 2{|v|-2}
You know, |V| + |R| = |E| + 2
K.|R| ≤ 2|E|
K(|E| - |V| + 2) ≤ 2|E|
(K - 2)|E| ≤ K(|V| - 2)
|E| ≤ 
- 2{|V| - 2}
5. If 'G' is a simple connected planar graph, then
There exists at least one vertex V∈ G, such that deg(V) ≤ 5
6. If 'G' is a simple connected planar graph (with at least 2 edges) and no triangles, then
Theorem: Let G be a connected planar graph with p vertices and q edges, where p ≥ 3. Then q ≥ 3p − 6.
Proof:
Let r be the number of regions in a planar representation of G. By Euler’s formula, p − q + r = 2.
Now the sum of the degrees of the regions equals 2q
But each region has degree 3 or more;
Hence 2q ≥ 3r, Thus r ≥ 2q/3
Substituting this in Euler’s formula gives
Multiplying the inequality by 3 gives 6 ≤ 3p − q which gives us our result.
Note- The theorem is not true for K1 where p = 1 and q = 0, and is not true for K2 where p = 2 and q − 1.
Key takeaways
- For any planar graph with v vertices, e edges and f faces, we have-
2. A graph 'G' is said to be planar if it can be drawn on a plane or a sphere so that no two edges cross each other at a non-vertex point.
References:
- Edgar G. Goodaire and Michael M. Parmenter, Discrete Mathematics with Graph Theory,3rd Ed., Pearson Education (Singapore) P. Ltd., Indian Reprint, 2005.
- Kenneth Rosen Discrete mathematics and its applications Mc Graw Hill Education 7th edition.
- V Krishna Murthy, V. P. Mainra, J. L. Arora, An Introduction to Linear Algebra, Affiliated East-West Press Pvt. Ltd.
- J. L. Mott, A. Kendel and T.P. Baker: Discrete mathematics for Computer Scientists and
- Mathematicians, Prentice Hall of India Pvt Ltd, 2008.
- Schaum’s outlines discrete mathematics.
- Discrete mathematics structures by G.Shanker rao.
