Graph Theory – Quick Guide For Beginners

Graph theory has applications in all of these and thus is quite popular, be it mathematics, computer science, biosciences, information technology, or linguistics. 

So, it is only natural that you are curious to study more about graph theory.

This article brings you a guide to graph theory to help you understand its concepts.

Graph Theory is defined as the study of graphs or mathematical structures used to model relations between objects.

These mathematical models mostly deal with the edges and vertices and their relationships with each other.

Table of Contents

Data structures: Trees and Graphs

We have always been confused if trees and graphs are the same or different data structures.

Well yes. They are almost the same. 

Trees are networks or graphs having root nodes that connect with other child and leaf nodes and are always defined by a set of rules. The graphs have no restrictions and no root nodes. 

In graphs, the nodes can be connected in any way possible, and unlike trees, graphs do not need to be “one-directional.”

A tree is always a graph or a network, but a graph or a network will not always be a tree.

Applications of Graph theory

Social, Physical, Information, and Biological systems all of their in-between relationships and processes can be modelled using graphs.

For example, most computer science students must be aware of the terms of networks and networking. Networks are also a kind of graph with attributes (such as routers, computer systems, etc.) associated with vertices and edges.

Now that you know about graphs let us tell you a few applications which will help increase your curiosity and better understand graph theory.

1. Computer Science

Graphs can represent communication networks, computational devices, data organization, computation flow, etc.

The problems of social media, biology, mapping of neurodegenerative diseases, travel, computer chip design, and many other fields make use of the edges and nodes concept of graphs. 

Computer scientists can use graph or network transformation systems to generate graph databases that allow safe transactions, querying network-structured data and persistent storage.

2. Mathematics

Geometry, a concept in mathematics, makes the most use of graphs. Knot theory, which is a part of topology, also makes use of graphs.

The Algebraic graph theory is applied to many areas, including complexity and dynamic systems, and has close links with group theory.

3. Linguistics

Due to better compatibility between natural language and discrete structures, linguistics has found various uses of graph theory methods.

For instance, syntax and compositional semantics, which are traditional approaches, follow tree-based or hierarchical network or graph models.

The head-driven phrase structure grammar, a contemporary approach in natural language, is modelled using typed feature structures or directed acyclic graphs.

Many organizations, such as TextGraphs, WordNet, VerbNet, etc., have come into play due to many uses of graphs in linguistics.

4. Social Sciences

Sociology uses graph theory to analyze social networks to explore rumor spreading or measure actors’ prestige in these networks.

Other graphs include acquaintanceship graphs, friendship graphs, influence graphs, collaboration graphs, etc., all of which study people’s behavior.

5. Physics and Chemistry

You’d be surprised to know, but graph theory has found its way into physics and chemistry by making its use in the study of molecular networks.

It is used in physics to study condensed matter physics and the three-dimensional atomic structures and networks using graph-theory statistics related to atom topology.

The quantum field theory in physics can be summarized using Feynman graphs and rules of calculation.

Graph theory has also found its usability in computational neuroscience, representing functional connections between brain areas related to various cognitive processes. 

6. Biology

Graph theory is instrumental in conversation efforts of various species in biology in which the habitats of certain species are represented as nodes and their migration paths as edges.

It is also useful in modeling and analyzing datasets with complex relationships such as clustering cells into cell-types in single-cell transcriptome analysis.

Graphs are also used to model genes or proteins and study their relationships, such as gene regulatory networks and metabolic pathways.

The nervous system is a network or graph with neurons as vertices and the connections between them as edges.

7. General

You should have observed the city routes or networks sometime. Graphs can easily represent them.

The hierarchical information from your family tree can also be depicted by a tree data structure, a particular mathematical model type.

Let’s talk about the basics

The graph theory is a part of the graph or network concept that computer science has borrowed because it has coding applications.

Before we move forward with the graph theory, let’s understand some basic concepts or fundamentals.

1. Point

A point, represented by a dot, is a position defined in a one-, two-, three-dimensional space and is denoted by an alphabet.

For example, 

Here, ‘x’ is the point.

2. Vertex

It is a meeting point of multiple lines and is also known as a node. An alphabet denotes it.

For example,

Here, ‘x’ is the vertex.

3. Line

A connection between two points is called a line.

For example,

Here the link between the two points’ x’ and ‘y’ is called a line.

4. Edge

An edge is a path or a line that connects two vertices, namely- starting vertex and ending vertex.

Many edges can be formed; thus, at least one vertex must form an edge.

For example, 

Here, the link between the vertex ‘x’ and ‘y’ is called an edge.

5. Parallel edges

If there are more than one edge between two vertices, the edges are parallel.

For example, 

In the above graph, between the two vertices ‘q’ and ‘w,’ there are two edges, and thus these edges are called parallel edges.

6. Graph

A graph ‘g’ is a network, or a mathematical model formed using edges and nodes.

It is denoted by ‘G,’ which is defined as G = (V, E) where ‘V’ is the set of vertices and ‘E’ is the set of edges.

For example,

The above network or graph can be defined using its vertices and edges, which are:

V= {a, b, c, d}

E= {ab, bc, cd}

7. Multigraph

A graph or a network that contains parallel edges is called a multigraph.

For example,

The above network is a multigraph because there are two edges between its vertices ‘b’ and ‘c’.

8. Loop

The structure that you get when an edge has the same starting and ending vertex is called a loop, i.e., it is a graph with an edge drawn from the vertex to itself.

For example,

The above graph can be defined using its vertices and edges, which are:

V= {a, b, c, d}

E= {aa, ab, bb, bc, cd, da}

The loops are at vertices a and b.

9. Adjacency

The norms of adjacency are different for edges and nodes of a graph or a network. They are:

(i) If an edge is present between two vertices, then they are said to be adjacent or in adjacency with each other, and this adjacency is maintained by that single edge connecting the two vertices.

(ii) If a typical vertex is present between two edges, then the edges are said to be adjacent or in adjacency, and that single vertex present maintains the adjacency between the two edges.

For example,

In the above graph, the adjacency of edges and vertices can be defined as:

  1. Vertices a and b are adjacent because they are connected by a common edge ab.
  2. Vertices c and d are adjacent because they are connected by a common edge cd.
  3. Edges ab, ac and ad are adjacent because they are connected by a common vertex a.
  4.  Edges bc and cd are adjacent because they are connected by a common vertex c.

What is a graph?

Graphs are data structures or networks that have two main components: a node and an edge.

Node: The vertex of a graph or network is known as a node N or vertex V.

Edge: Connection between two nodes, say u, v, identified as a unique pair (u, v) is known as an edge E or an ordered pair. Sometimes the edges of the graph might have some associated with them. Note- Always remember that (u, v) and (v, u) are not the same and hence are known as ordered pairs and are unique. 

A graph g can be understood as a network or a pictorial representation of a set of (V, E), where there are a set of vertices V and a set of edges E.

For example:

In this network,

V or N = {a, b, c, d, e, f}

E = {ab, bc, 

Types of Graph

1. Directed Graphs

Graphs or networks whose edges have orientations and are defined as an ordered pair G = (V, E) where ‘V’ is a set of vertices and ‘E’ is the set of edges consisting of ordered pairs of vertices.

For example, 

In the above given directed graph, we have an edge (a, b) and vertices a and b. These nodes are known as the endpoints with node ‘a’ being the tail and node ‘b’ being the edge’s head.

2. Undirected Graph

A graph or a network with no defined direction edge is said to be an undirected graph. 

Undirected graph G is an ordered pair G = (V, E), where E is the set of unordered pairs of vertices.

For example, 

In an edge (a, b), the pair of vertices a and b are known as the endpoints, with the edge joining the two vertices incident on them.

3. Cycle Graph

If a simple graph or network with ‘n’ vertices has ‘n’ edges of length ‘n’, then such a network is known as a cycle graph.

The number of vertices should be greater than or equal to 3, and the vertex degree should be two.

For example,

The above simple graph is a cycle graph as it has greater than or equal to 3 edges and the degree of vertex = 2.

4. Acyclic graph

A directed graph with no cycle is said to be a Directed Acyclic Graph or DAG. A network will be called DAG if a vertex ‘v’ in DAG will have no directed edge either starting or ending on ‘v.’

Note: It can be both directed and undirected.

For example,

In the above figure, there are no cycles, so the graph is acyclic or non-cyclic.

5. Cyclic Graph

Opposite to the acyclic graph, an acyclic graph is a network having at least one cycle.

For example, 

In both the above graphs, the edges form a cycle, which means that the network is cyclic.

6. Connected graph

When there is a defined path between every pair of vertices and no node is unreachable, the graph or the network is called a connected graph. 

In connected graphs, there should be at least one edge between every two vertices in the network.

See also  Download Turbo C++ for Windows 7, 8, 8.1, and Windows 10

For example,

The above network is connected because all the vertices are connected through defined edges.

7. Disconnected graph

Unlike a connected graph, a disconnected network or graph is formed when at least two vertices are not connected.

For example,

The above network is a disconnected graph since two of the vertices are not connected.

8. Complete graph

In a complete graph ‘g,’ every node ‘x’ is adjacent to every node ‘y’ so that there is an edge present between every pair of the vertices. 

The Complete graph will have ‘n’ mutual vertices and is denoted by ‘Kn’.

For example,

Verticesabcd
aNot ConnectedConnectedConnectedConnected
bConnectedNot ConnectedConnectedConnected
cConnectedConnectedNot ConnectedConnected
dConnectedConnectedConnectedNot Connected

The graph is complete in the above figure because all of its vertices are connected with other vertices.

9. Biconnected graph

A graph with no articulation point cannot be broken down further into subsequent pieces by deleting vertices called a biconnected graph.

Thus, biconnected graphs cannot be disconnected even if one of the vertices was to be removed.

For example,

In the above graph G, we can see that even if we remove one vertex from the above graph, it will still be connected.

10. Null graph

A graph with no edge is said to be a null graph.

For example,

In the above figure, there are four vertices but no edges connecting them. Thus, it is a null graph.

11. Trivial graph

A graph that is made of only one vertex and no edge is called a trivial graph. It is a dot on a plane.

For example,

In the above figure, the vertex ‘q’ denotes a trivial graph.

12. Simple graph

If a graph has no loops and no parallel edges, then such a graph is known as a simple graph.

For these graphs, if there are ‘n’ vertices, there can be a maximum of nC2 edges, and 2^(nC2) graphs possible, where nC2 = n(n-1)/2.

For example,

There are four vertices and three edges in the above figure, and no loops or parallel edges.

Here if we see, 

Then as per our formula of nC2 with n=4, we see that the maximum number of edges possible is,

 nC2 = n(n-1)/2

       = 4(4-1)/2 = 6

Also, the maximum number of graphs possible with 4 vertices are,

2^( nC2) = 2^4 = 16

Why don’t you try and create those 16 graphs and see if the formula is right?

It will be fun.

13. Regular graph

If all the graph vertices have the same degree, then such a graph is called a regular graph. 

The graph’s degree defines its name, i.e., a ‘k’ vertices graph called a ‘k-regular graph.’

For example,

In the above graph, all vertices have the same degree = 2 and thus is a regular graph.

14. Wheel graph

When a new vertex, called a hub, is added to a cycle graph Cn-1, a wheel graph is obtained, denoted by Wn.

This hub is connected to all the vertices of Cn.

To calculate the total number of edges in a wheel graph we have, 

Number of edges = number of edges going from hub to other vertices + several edges going from all other nodes in a cycle without a hub.

=(n-1) + (n-1)

=2(n-1)

For example,

In the above graph, a central vertex ‘e’ is connected to other vertices in the cycle graph. Thus, it is a wheel graph.

15. Bipartite graph

If in a graph G = (V, E), every edge in set E joins a vertex in set V1 to another vertex in set V2, then the graph is called a bipartite graph vertex partition V = (V1, V2).

Thus, we can say that in a bipartite graph, every edge joins two vertices from a different set of vertices.

For example,

In the above graph, the edge is joining the two vertices in a crisscrossed manner.

16. Complete bipartite graph

Unlike a simple bipartite graph, every vertex from both vertices V1 and V2 are connected by an edge in a complete bipartite graph.

However, remember that a complete bipartite graph is not a complete graph and should be confused.

A complete bipartite graph is represented by K (a, b), where a is the number of vertices in V1 and b is the number of vertices in V2.

Thus, it can be concluded that the graph, K (a, b), has a total of’ ab’ edges connecting (a+b) vertices, which can be made similar to a regular graph if, a=b.

For example,

There is an edge between each vertex connecting the two sets of vertices with each other.

17. Star graph

Denoted by K (1, n-1) Star graph is a special case of a bipartite graph where there is one vertex in V1 and (n-1) vertices in V2 or vice versa.

In other words, A complete bipartite graph in which all vertices from one set connect with a single vertex is called a star graph.

For example,

In the above figure, all the vertices converge or meet at the same vertex. This is a star graph in which vertex V1 = {a} and V2 = {p, q, r, s} .

18. Complement of a graph

We know that a graph consists of edges and vertices (V, E). 

A complement of a graph ‘G-‘ is a graph containing all the vertices as a graph, but the edges will only be those absent in the graph.

Thus, if the edges present in one are not similar to the other in two graphs,i.e., both have the same set and alignment of vertices, both the graphs are known as a complement.

A complete graph can be formed by merging two adjacent graphs.

Thus, 

|E(G1)| + |E(G2)| = |E(G)|,

Where G1 and G1 are complement graphs, and G is the complete graph.

For example,

In the above graphs, we can see that graph ‘I’ and graph ‘II’ complement each other as they have no same edges but the same vertices. Also, on merging, we get a complete graph.

Trees and Forest

Now that we have understood graphs and their types, let’s quickly see the trees and forest and how they are a graph.

First, we will see about trees.

Tree

Trees are Acyclic and Connected Graphs with restrictions. The most important restriction is that a child node can have only one parent node.

As we have read earlier, a tree is always a graph, but a graph may not be a tree.

Trees are special networks or graphs representing hierarchical structures in a mathematical model and are classified as the simplest type of graphs with a rich structure.

Be it the family tree of a computer science problem, trees have proven to be quite useful.

There are a few definitions related to trees:

1. Root node: The topmost node or vertex in a tree is called a root node. Trees start their hierarchical structure from this node.

2. Leaf nodes: The nodes with no child and are the last nodes in a tree are called leaf nodes.

3. Child nodes: The nodes which are not root nodes or leaf nodes are called child nodes. They are the descendants of the root node with more child nodes.

4. Branches: The edges of the tree connecting various nodes are called branches.

Mathematically, if a tree has ‘n’ nodes, then it has ‘n-1’ edges.

If the edges become ‘n’, it will have to pair with two vertices, giving rise to a cyclic graph, and trees can never be cyclic.

For example,

The above network is a hierarchical structure with acyclic edges. It is a tree.

Root node: a

Child nodes: b, c, d

Lead nodes: e, f, g, h

Branches: ab, bc, bd, ce, cf, dg, dh

Spanning trees

If the sub-graph of a connected graph is forming a tree, it is called a spanning tree. 

For a sub-graph to be a spanning tree, two conditions need to be satisfied:

(i) It should be a tree

(ii) All vertices of the graph must be present.

For example,

In the above graphs X and Y, X is a connected graph, and Y is a sub-graph of X, which is a tree as it has no cycles. Thus, Y is a spanning tree.

Circuit rank

The number of edges that should be deleted from a connected graph to obtain a spanning tree is called the connected graph’s circuit rank.

Suppose there are ‘v’ vertices and ‘e’ edges in a connected graph ‘G’ from which a spanning tree of (v-1) edges is formed.

Since a spanning tree contains ‘v-1’ edges, thus we need to keep that many edges out of ‘e’ to form a spanning tree with no cycles.

Thus, the circuit rank of the connected graph = e – (v-1).

For example,

In the above spanning tree example, the connected graph X, has

Number of Edges = 12

Number of Vertices = 11

Thus, circuit rank = Number of edges – (Number of vertices – 1)

= 12 – (11 – 1)

= 2

Therefore, the spanning tree we got, i.e. Graph Y is correct.

Kirchoff’s theorem

If you need to find the number of spanning trees that can be formed from a connected graph, then Kirchoff’s theorem can be used.

The theorem, which is a generalization of Cayley’s formula, states that the number of spanning-trees from a connected graph can be calculated in polynomial time using the Laplacian determinant matrix.

The Laplacian matrix of a graph is equal to the difference between the graph’s degree matrix and its adjacency matrix.

For example,

Consider the above figure.

Here the matrix L can be filled using 1s and 0s by denoting the edges present or absent in the matrix respectively, i.e., if an edge is present, then 1, and if absent, then 0.

L = 

abcd
a11
b111
c11
d111

On simplifying we get:

11
111
11
111

Using Kirchoff’s theorem, the above matrix’s principal diagonal will be replaced by the degree of vertices, and rest terms will be multiplied by -1.

2-1-1
-13-1-1
-12-1
-1-1-13

On removing row 1 and column 1, we get,

L=

3-1-1
-12-1
-1-13

The determinant of the above matrix = 8.

Thus, there will be 8 spanning trees possible.

Forest

If we go by the English dictionary definition of forest, then it can be called a collection of trees.

The same is true in terms of graph theory as well.

A disconnected acyclic graph, a disjoint collection of various trees, is known as a forest.

For example,

If we look at the above two graphs, we can see that these are single disconnected or disjoint graphs with no cycles. Thus, it is a forest.

Degree of Vertex

The total number of vertices adjacent to a vertex ‘X’ is called the degree of a vertex and is denoted by deg(V) defined as,

Deg(v) <= n-1 where, v belongs to G.

Since a vertex can form edges with all other vertices in a graph except itself, the vertex’s degree can be a maximum of the total number of vertices in that graph – 1.

Depending on the degree of vertices, there are two types of vertices:

(i) Pendent vertex

If the degree of a vertex is 1, then it is called a pendent vertex. Such vertices have only an edge connecting them to one other vertex.

For example,

The vertex is a pendent vertex in the above figure because there is only an edge towards it. Thus, it is a pendent vertex.

(ii) Isolated Vertex

If the degree of a vertex is 0, then it is called an isolated vertex. Such vertices have no edges connecting them to other vertices.

For example,

In the above figure, the vertex is isolated as no edges are going from it. Thus, it is an isolated vertex.

Depending on the below two graphs, the degree of vertex differs:

(i) Directed Graph

(ii) Undirected Graph

1. Degree of Vertex – undirected graph

Let us understand this using an example:

Consider the below graph,

In this graph, there are 5 vertices. Now, the degree for each vertex will be:

deg(a) = 2

deg(b) = 3

deg(c) = 3

deg(d) = 2

deg(e) = 3

2. Degree of vertex – directed graph

A graph having directed edges is called a directed graph. In this graph, each vertex has:

(i) Indegree: These are the number of edges coming towards the vertex ‘A’ and are denoted by deg-(A).

(ii) Outdegree: These are the number of edges going from the vertex ‘A’ and are denoted by deg+(A).

For example,

Considering the below-directed graph, the

Vertices, V = {a, b, c}

Edges, E = {ba, da, cb, cd, db}

Let us calculate the indegree and outdegree for each of its vertices:

  1. Indegree

(i) deg-(a) = 2

(ii) deg-(b) = 2

(iii) deg-(c) = 0

(iv) deg-(d) = 1 

  1. Outdegree

(i) deg+(a) = 0

(ii) deg+(b) = 1

(iii) deg+(c) = 2

(iv) deg+(d) = 2

The degree sequence of a graph

If the arrangement of degrees of all vertices in a graph is either ascending or descending, then the order or sequence obtained is called the degree sequence of that graph.

See also  Download Turbo C++ for Windows 7, 8, 8.1, and Windows 10

For example,

In the above figure, the

Vertices V = {a, b, c, d}

Edges E = {ab, bc, cd, de, ec, eb, ea}

The degree of each vertex is:

deg(a) = 2

deg(b) = 3

deg(c) = 3

deg(d) = 2

deg(e) = 4

Thus, the degree sequence for vertices {a, d, b, c, e} in ascending order is: {2, 2, 3, 3, 4}

And the degree sequence for vertices {e, b, c, a, d} in descending order is: {4, 3, 3, 2, 2}

Sum of Degrees of vertices theorem

For a non-directed graph = (V, E) with vertices V = {V1, V2, …., Vn}, the sum of degrees of vertices will be

n Σ i=1 deg(Vi) = 2*|E|

Corollary 1

In a non-directed graph, there are even several vertices having an odd degree.

Corollary 2

For a non-directed graph = (V, E) with vertices V = {V1, V2, …., Vn}, sum of degrees of vertices will be

n Σ i=1 deg+(Vi) = |E| = n Σ i=1 deg-(Vi).

Corollary 3

In a non-directed graph, if the degree of each vertex, deg(V) <= k then,

K|V| <= 2|E|

Corollary 4

In a non-directed graph, if the degree of each vertex, deg(V) = k then,

K|V| = 2|E|

Corollary 5

In a non-directed graph, if the degree of each vertex, deg(V) >= k then,

K|V| >= 2|E|

Coloring

At one time or other, we all have used colored sticky notes to label our important notes for easy reference and understanding.

We all must have seen detectives in TV series and movies mapping networks with different colors.

The same goes for the coloring of graphs in graph theory.

Coloring in graphs is a realistic way to label various graphical components such as edges, constraint regions, and vertices in graphical networks.

For coloring a graph, various constraints such as a set of graph colors, method of assigning colors, and order of coloring, etc., need to be kept in mind.

Vertices with the same color are part of independent sets.

A colored graph with an appropriate chromatic number is called a properly colored graph.

Chromatic Number: As a rule, no two adjacent vertices, edges, or regions can be colored with a minimum number of colors known as the chromatic number and is denoted by C(G).

It can be defined as the minimum possible number of colors that are required for coloring a graph.

For a graph with no edges, the chromatic will be 1, where for others, it will be greater than or equal to 2.

For example,

Here no adjacent vertices are of the same color. Also, since there are 3 number of colors used in the graph, the chromatic number will be: 3

1. Vertex coloring

The allotment of colors to the vertices of a graph such that no adjacent vertex, i.e., vertices with a standard edge, have the same color is known as vertex coloring.

2. Region Coloring

The assignment of different colors to different regions in a plane such that no two adjacent regions, i.e., regions with the same edge, have the same color as region coloring.

For example,

In the below graph, the regions green and blue are said to be adjacent because they have a common edge ‘ac’ between them.

Thus, the graph can be colored as follows:

Applications of Graph Coloring

Being one of the essential applications of graph theory, many real-time applications use it. 

It is primarily used in computer science as follows:

  • Image segmentation
  • Process Scheduling
  • Clustering
  • Image Capturing
  • Resource Allocation
  • Data Mining
  • Networking

Connectivity

For traversing a graph from one vertex to another, the graph must be connected. 

To decide whether a graph is connected or disconnected, we need to check its connectivity, which is different for edge and vertex.

From the definition of connected graphs, we know that if there is an edge between each vertex in a graph, it is called a connected graph.

Thus, if there is a path or link to traverse every vertex in the graph, it is called a graph’s connectivity.

On the other hand, a graph with disconnected if there are multiple disconnected edges and vertices in the graph.

For example,

In the above graph, all vertices are connected to each other as there is an edge between each vertex.

Cut vertex

In a connected graph’ G,’ if one deletes or cuts ‘G-V,’ we get a disconnected graph, then that vertex V belonging to G is called a cut vertex.

An ‘n’ vertices graph can have a maximum of (n-2) cut vertices.

For example,

In this graph, the vertices c and e are cut vertices.

Vertex connectivity

Vertex connectivity is defined as the minimum number of vertices required to be removed so that a connected graph is converted to a disconnected graph.

It is denoted by K(G), and for any connected graph G,

K(G) ≤ ƛ(G) ≤ δ(G)    ………… (i)

Where,

K(G) = Vertex connectivity

ƛ(G) = Edge Connectivity

δ(G) = minimum number of degree of G

For example,

In the above graph g, if we delete vertex d and c, then a disconnected graph will be formed.

Here,

δ(G) = 2

Deleting edges ‘ce’ and ‘ad’ gives a disconnected graph, thus ƛ(G) = 2

Putting values of δ(G) and ƛ(G) in equation (i) we get,

K(G) ≤ 2 ≤ 2

Thus, K(G) = 2

Cut edge (bridge)

Like a cut vertex, if from a connected graph, an edge is deleted such that it results in a disconnected graph, then such edges are called cut edges.

For a connected graph ‘G’ having ‘v’ vertices, 

There is at least one cut vertex for every cut edge; however, vice versa is not valid.

For every cut vertex, there may or not be a cut edge associated with it.

An edge can be a cut edge only if the edge is a part of any cycle.

There is a maximum of ‘v-1’ cut edges possible.

For example,

In the above graph, the edge (c,e) is cut edge.

Edge connectivity

The minimum number of cut edges or the smallest cut set of a graph that is required to convert a connected graph into a disconnected graph is called edge connectivity and is denoted by ƛ(G).

For example,

Here, we can see that the graph becomes disconnected if we remove edges ‘bc’ and ‘gf’ from the graph. Thus the edge connectivity will be 2.

Cut set of a graph

If deletion of a set of edges E’ from a connected graph makes the graph disconnected and generates a disconnected graph, the subset E’ formed from set E edges is called the graph’s cut set.

In other words, the set of deleted edges that convert a connected graph into a disconnected graph is called the cut set of the graph.

For example,

In the above graph, if we remove edges ‘bc’ and ‘gf’ we get a disconnected graph.

Thus, the cut set, E’ = {bc, gf}

Independent Sets

For a set to be an independent set,

(i), there shouldn’t be any adjacent edges and any common vertex between two edges.

(ii) there shouldn’t be any adjacent vertices and any typical edges between two vertices.

1. Independent vertex Set

A subset ‘S’ of vertices ‘V’ in a graph ‘G’ = (V, E) is said to be an independent vertex set if there are no adjacent sets of vertices in ‘S.’

For example,

In the above graph,

The possible subsets are:

S1 = {b}

S2 = {b, e}

S3 = {c, f}

S4 = {a, e}

Here, the subsets S2, S3, and S4 are an independent vertex because they contain at least two vertices from the graph and none of the vertices are adjacent. Subset S1 is not an independent vertex set because it contains only one vertex.

The maximal Independent vertex set

An independent vertex set is the maximal independent vertex set of a graph’ G’ if no other vertices are added to the subset.

For example,

In the above graph, S2, S3, and S4 are independent vertex sets. Since it is not possible to add more vertices in any of these subsets, hence they are maximal independent vertex sets.

The maximum independent vertex set

A maximal independent vertex set can be called a full independent vertex set if the maximal set contains the maximum number of vertices.

For example,

In the above graph, S2, S3, and S4 are maximal independent vertex sets and the maximum number of vertices in each subset is 2. Thus, all these subsets are maximum independent vertex sets. 

2. Independent Line Set

A subset L of a graph is an independent line subset if there are no adjacent edges present in L.

For example,

In the above graph,

The possible subsets are:

L1 = {a, d} {e, f} {b, c}

L2 = {a, b} {c,e}

L3 = {a,c}

L4 = {e, f} {a, c} 

Here, the subsets L1, L2, and L4 are independent line sets because there are at least two edges from the graph, and none of the edges are adjacent to each other. The subset L3 is not an independent line set because it contains only one edge.

Maximal Independent Line Set

An independent line set is the maximal independent line set of a graph’ G’ if no other edges can be added to the subset.

For example,

In the above graph, it is possible to add more vertices in subset L2. Thus, subsets L1 and L4 are maximal independent line sets.

Maximum independent line set

A maximal independent line set can be called a full independent line set if the maximal set contains the maximum number of edges.

For example,

In the above graph, the subsets L1 and L4 are maximal independent line subsets with maximum number of edges in L1 = 3 and in L4 = 2. Thus, L1 is the maximum independent line set.

Coverings

A subgraph covering either all the vertices or all the edges of a graph is called a covering graph.

It can be of two types:

(i) Line Covering – A subgraph containing all the vertices is called a line covering or an edge covering graph.

(ii) Vertex Covering – A subgraph containing all the edges is called a vertex covering graph.

1. Line covering

A subgraph, C(E), of a graph G = (V, E) is called a line covering graph if there is at least one edge C on which every vertex of G is incident, i.e., each vertex should be connected with another vertex by an edge. 

Thus,

Deg(V) >= one where every V belongs to G

Note: A graph with isolated vertex will not have line covering. The line covering of a graph with ‘x’ vertices has at least [1/2] edges.

For example,

In this graph, the subgraphs with line covering are:

C1 = {{a, d}, {d, b}, {b, c}}

C2 = {{a, b}, {a, c}, {b, d}}

C3 = {{c, d}, {a, d}, {b, c}}

C4 = {{a, d}, {b, c}}

C5 = {{a, c}, {b, d}} 

Minimal line covering

A minimal line covering of a graph is the one in which no further edges can be deleted from C(E).

For example,

In the above graph, the line covering subgraphs are:

C1 = {{a, d}, {d, b}, {b, c}}

C2 = {{a, b}, {a, c}, {b, d}}

C3 = {{c, d}, {a, d}, {b, c}}

C4 = {{a, d}, {b, c}}

C5 = {{a, c}, {b, d}} 

Since edge {d, b} can be deleted from C1 and edge {c, d} can be deleted from C3, both these subgraphs are not minimal line coverings. Thus, C2, C4, and C5 are minimal line coverings.

Minimum line covering

The smallest minimal line covering, or the minimal line covering with the smallest or minimum number of edges, is called minimal line covering.

‘G’ (α1) is called the line covering number, which is the number of edges in the minimum line covering.

There are specific points to remember for minimum line covering:

  • Every line covering may or may not contain minimum line covering.
  • If a line covering does not contain paths of length equal to or more than 3, then that line covering is called a minimal line covering. This is because all line covering components are star graphs from which no edge can be deleted.
  • Every line covering contains minimal line covering.
  • A cycle is not possible in minimal line covering.

For example,

In the above example, 

In the above graph, the line covering subgraphs are:

C1 = {{a, d}, {d, b}, {b, c}}

C2 = {{a, b}, {a, c}, {b, d}}

C3 = {{c, d}, {a, d}, {b, c}}

C4 = {{a, d}, {b, c}}

C5 = {{a, c}, {b, d}} 

As we saw previously, C2, C4, and C5 are minimal line coverings. In this C4 and C5 are minimum line coverings because they have the minimum number of edges.

2. Vertex covering

A vertex covering graph is a subgraph ‘R’ of graph G = (V, E) in which every edge of the graph is incident on a vertex in ‘R.’

See also  Download Turbo C++ for Windows 7, 8, 8.1, and Windows 10

For example,

From the above graph G, the following subgraphs can be formed:

R1 = {a, c}

R2 = {b, d}

R3 = {a, d, b}

R4 = {a, b, c}

Among these, R1, R2, R3, and R4 are vertex covering subgraphs.

Minimal vertex covering

A minimal vertex covering of a graph G is the one in which no other vertex can be deleted from C(E).

For example,

In the above graph, the vertex covering subgraphs are:

R1 = {a, c}

R2 = {b, d}

R3 = {a, d, b}

R4 = {a, b, c}

In this, we can delete vertex ‘b’ from R4, thus R4 is not a minimal vertex covering. R1, R2, and R3 are minimal vertex coverings.

Minimum vertex covering

The smallest minimal vertex covering, or the minimal vertex covering with the smallest or minimum number of vertices is called minimal vertex covering.

‘G’ (α2) is called the line covering number, the number of vertices in the minimum vertex covering.

For example,

In the above example, the line covering subgraphs are:

R1 = {a, c}

R2 = {b, d}

R3 = {a, d, b}

R4 = {a, b, c}

Amongst these four, the minimal line covering subgraphs are R1, R2, and R3. Since, R1 and R2 have the minimum number of vertices, thus they are minimum vertex coverings.

Basic Properties

Every graph in graph theory has a few properties defined for it in specific terms used to characterize them depending on their structure.

These specific terms are about the domain of graph theory and are common to all graphs. 

Distance between two vertices

There can be several edges between two vertices, and thus the shortest path or distance between the two is called the distance between two vertices denoted by d(U, V) where U and V are vertices between whom distance needs to be found.

For example, 

There are two paths to reach vertex A from vertex D, but the shortest path between them is ae -> ed. Thus, this path will be considered as the distance between these two vertices.

The eccentricity of a vertex

The eccentricity of a vertex, denoted by e(v), is defined as the maximum of the distances calculated from a vertex to all other vertices.

For example,

In the above graph, the distance between ‘b’ and all other vertices are:

Distance from ‘b’ to ‘a’: 1

Distance from ‘b’ to ‘c’: 1

Distance from ‘b’ to ‘e’: 2

Distance from ‘b’ to ‘d’: 3

Distance from ‘b’ to ‘f’:  3

Thus, the eccentricity of vertex ‘b’, e(b) is 3.

Similarly, eccentricities for all other vertices are:

e(a) = 3

e(c) = 2

e(d) = 3

e(e) = 2

e(f) = 3

The radius of a connected graph

The radius of a connected graph, denoted by r(G), is the minimum amongst all the eccentricities, or the minimum amongst all maximum distances of a vertex to all other vertices.

For further simplification, we can say that the minimum among all the eccentricities in a graph G is the radius of the graph G.

For example,

In the above network or graph, the eccentricities of the vertices are:

e(a) = 3

e(b) = 2

e(c) = 2

e(d) = 3

e(e) = 2

e(f) = 3

Thus, the radius of the graph, r(G) = 2 as it is the minimum amongst all eccentricities.

The diameter of a graph

Contrary to the radius of a connected graph, a connected graph’s diameter is the maximum eccentricity amongst all other eccentricities.

Thus, if the maximum among all maximum distances between a vertex and all other vertices is denoted by d(G). 

For example, 

Based on the above network or graph, the eccentricities of the vertices are:

e(a) = 3

e(b) = 2

e(c) = 2

e(d) = 3

e(e) = 2

e(f) = 3

Thus, the diameter of the graph, d(G) = 3 as it is the maximum amongst all eccentricities.

Central point

The graph’s central point is the vertex whose eccentricity is equal to the radius of the graph.

Thus, if e(V) = r(V), 

then the vertex V is the Center of the graph G.

For example, 

Based on the above network or graph, the eccentricities of the vertices are:

e(a) = 3

e(b) = 2

e(c) = 2

e(d) = 3

e(e) = 2

e(f) = 3

The eccentricity of vertices ‘b’ and ‘e’ are equal to the radius of graph, i.e., r(G) = e(b) = e(e) = 2. Thus, the vertices ‘b’ and ‘e’ are the central points of the graph.

Center

The Center of the graph is defined as the set of central points of graph G.

For example,

Based on the above graph, the Center of the graph is {b, e}.

Circumference

The number of edges that are part of the most extended cycle in graph G is called the circumference.

For example,

Based on the above graph, the longest cycles are a-b-c-a or d-e-f-d. Thus the circumference of the graph is 3.

Girth

Contrary to a graph’s circumference, girth is defined as the number of edges of the smallest cycle in graph G. 

It may or may not be the same as circumference based on the graph.

For example,

Based on the above graph, the smallest cycles are a-b-c-a or d-e-f-d. Thus the girth of the graph is 3.

Traversability

Traversing a graph is done by drawing a path between the vertices without going back on the same path.

In this article, we will understand two main concepts of graph traversing:

(i) Euler’s path

(ii) Hamiltonian Path

1. Euler’s Path

If there is an Euler path present in connected or directed graphs ‘G,’ then such a network is traversable. 

There should be exactly one edge of ‘G’ and at least one vertex of ‘G’ in an Euler path.

If the starting and end vertex of an Euler path is the same, then such a path is called Euler circuit.

For example,

In the above graph, Euler path is: d-a-b-d-c-b

Euler’s Circuit theorem

According to Euler’s Circuit theorem, connected graphs can be traversable, iff (if and only if) there are exactly 2 or 0 vertices with an odd degree in G. 

The graph might also contain Euler’s path and not Euler’s circuit if it has only two vertices with odd degree.

Thus, for a graph to have Euler’s circuit it should have no odd degree vertices.

Considering the graph or network used in the above case the graph contains a Euler’s path d-a-d-b-c-b. This path is not an Euler’s circuit because there are two odd degree vertices,i.e., ‘b’ and ‘d’.

2. Hamiltonian Path

Before we learn about the Hamiltonian path, let’s have a look at the Hamiltonian graph.

A hamiltonian graph is a connected graph G in which there exists a cycle containing all the vertices of graph G.

In a Hamiltonian graph, each vertex of G exists only once, and the path formed is called a Hamiltonian path.

The Hamiltonian cycle is different from the Euler cycle because each edge of the graph exists only once in the Euler cycle. In contrast, in the Hamiltonian cycle, some edges of the graph can be skipped.

For example,

In the above graph we can say that:

Euler path exists – True

Euler circuit exist – False

A hamiltonian cycle exists – True

A hamiltonian path exists – True

Matchings

A subgraph with no edge adjacency or no common vertex between any two edges is called a matching subgraph.

Mathematically, a subgraph can be called a matching subgraph M(G) of a graph G = (V, E) if each vertex of G is incident on at most one edge in subgraph M.

Thus, deg(V) ≤ 1 for all V belonging to G.

In a matching subgraph, it should be remembered that two edges cannot be adjacent because in such a case, the degree of the vertex with adjacent edges will have degree two, which is against the matching rule.

While matching graphs,

If deg(V) = 1, then the vertex is said to be matched.

If deg(V) = 0, then the vertex is said to be not matched.

For example,

In this graph G, following four matchings without adjacency and covering all nodes c, f, e, d can be formed:

Using graphs and examples given above, you can try to form more network matchings.

Maximal matching

A matching subgraph M in which no further edges can be added to M is called a maximal matching subgraph.

For example,

Based on the above graph, M1 and M3 are the maximal matching subgraphs.

Maximum matching

The largest maximal matching subgraph or the maximal subgraph with the maximum number of edges is called the maximum matching subgraph.

The matching number is defined as the number of edges in the maximum matching subgraph.

For example,

In the above case, we have M1 and M3 as maximal matching subgraphs which are also the maximum matching subgraphs as both of them have the same number of edges.

Perfect matching

If each vertex in the subgraph has degree one, i.e., each vertex from graph G is incident on only one edge, then the subgraph is known as a perfect matching subgraph.

Thus, deg(V) = 1 for all V.

Note: Since no edges can be added into a perfect matching subgraph, it is also a maximum matching subgraph. But the vice versa is not valid.

Every maximum matching subgraph may or not be a perfect matching subgraph depending on the number of vertices |V(G)|. 

If the number of vertices is even, then it is a perfect matching subgraph.

If it is odd, then after matching each vertex, a single vertex will be left having degree zero, which is against the principle of perfect matching subgraphs.

For example, 

Using graphs formed in the above case, we can say that M1 and M3 are perfect matching subgraphs as each node has degree 1.

Isomorphism

Different forms of the same graph with the same number of edges, vertices, and edge connectivity, are called isomorphism, and such graphs are known as isomorphic graphs.

Isomorphic Graphs

If two graphs G1 and G2, have the same number of components and same edge connectivity, then such graphs are called isomorphic graphs.

Since G1 is similar to G2 thus,

|V(G1) | = |V(G2) |

|E(G1) | = |E(G2) |

Thus, it can be said that, in isomorphic graphs,

If vertices in one graph form a cycle, then vertices in the other will also form a cycle.

Also, the degree sequences of both graphs will be the same.

Example:

In this case, the above given undirected graphs are isometric as I1 and I2 have the same number of components(node, edge) and edge connectivity. 

Planar Graphs

A graph in which two edges do not cross each other at non-vertex points can be drawn on a plane or a sphere called planar graphs.

For example,

Graph 1:

Graph 2:

In the above graphs, Graph 1 is non-planar, and Graph 2 is planar. This is because it has no non-vertex intersecting edges.

Regions

The connected areas formed by a planar graph are called regions.

For example,

Graph Theory

Degree of regions

The degree of a bounded or an unbounded region is specified by the number of edges that enclose the region. It is given by,

r = deg(r) = Number of edges enclosing r.

For example,

In the above example, degree of every region is:

deg(Region 1) = 3

deg(Region 2) = 7

deg(region 3) = 3

Sum of Degrees of regions

For a planar graph of ‘n’ vertices, the sum of degrees of all the vertices is given by,

n Σ i=1 deg(Vi) = 2|E|

The sum of degrees of regions theorem states that a planar graph containing ‘n’ regions will have a sum of degrees of regions as,

n Σ i=1 deg(Ri) = 2|E|

Thus, it can be concluded that:

1. If D is the degree of each region, then the sum of degrees of regions will be:

D|r| = 2|E|

2. If the degree of each region ‘r’ is at least D, then the sum of degrees of regions will be:

D|r| ≤ 2|E|

3. If the degree of each region ‘r’ is at most D, then the sum of degrees of regions will be:

D|r| ≥ 2|E|

Now, assuming that all regions have the same degree and applying Euler’s formulae on planar graphs with |V| number of vertices, |R| number of regions, and |E| number of edges we have,

(i) |V| + |R| = |E| + 2 if graph G is connected planar.

(ii) |V| + |R| = |E| + (K+1) if it is a planar graph with ‘K’ components.

Homomorphism

On dividing some G’s edges with one or more vertices, if we can obtain more graphs such as G1 and G2, such graphs are called homomorphic graphs.

Homomorphism and isomorphism

If a graph G1 isomorphic to another graph G2, then it can be said that the graph G2 is homomorphic to the original graph G. However, the same cannot be said for the other way around.

Polyhedral graph

If each vertex of a simple connected planar graph is greater than or equal to 3, then such a graph is called a polyhedral graph.

Thus, deg(V) ≥ 3 for all V belonging to G.

Check out our Human Computer Interface guide which will be good for beginners.

Frequently Asked Questions

Recommended Articles