Understand Basic Concepts of Graph Theory With Python Implementation

This article talks about some basic concepts of graph theory and its applications using the Python programming language.
Graph theory

Graph, in simple terms, is a mathematical structure that depicts pairwise relationships among various entities. In computer science, graphs are non-linear data structures. This article talks about some basic concepts of graph theory and its applications using the Python programming language.

Graph Theory – An Overview

The graph is a way of diagrammatically representing a collection of interconnected nodes – each of which stands for an entity. A graph G is mathematically represented as an ordered pair (V, E), where V is the set of vertices and E is the set of edges. A network formed by vertices (or nodes) and the edges joining related vertices forms a graph. In practical applications, a graph can represent several complicated networks, such as a  


Sign up for your weekly dose of what's up in emerging technology.

Image source

  • A simple graph is one having no two edges connecting a common pair of vertices.
  • A multigraph can have multiple edges connecting a given pair of vertices. If there are say ‘n’ edges connecting a pair of vertices x and y, then {x,y} is an edge with a multiplicity of ‘n’.
  • An edge connecting a vertex to itself is said to form a loop.
  • A pseudograph is a multigraph having loops as well. 

Play with graphs!

This section describes some basic operations that we can perform on graphs and change their structures.


A subgraph of a graph (V, E) is a graph (X, Y) such that X is a subset of V and Y is a subset of E. A subgraph S of a graph G is said to be a ‘proper subgraph’ of G if S is not equal to G. 


Image source

Union of graphs

Union of graphs G1=(V1, E1) and G2=(V2, E2) results in a single graph with vertex set V=V1 U V2 and edge set E = e1 U E2. Here union operation ‘U’ plays the same role as that in set operations, i.e. it combines unique elements (vertices/edges) from each of the graphs.

union of graphs

Image source

Complement of a graph

Consider two graphs G1 = (V1,E1) and G2 = (V2,E2). If the edge(s) present in one of them is/are not present in the other and G1 and G2, when combined, form a complete graph, then G1 and G2 are said to be the complement of each other.

Note: A complete graph G(n) is a graph with ‘n’ vertices such that there exists exactly one edge joining each pair of the vertices.

Complement of a graph

Image source

Graphs I and II in the above figure are complement of each other.

Practical implemention

Here’s a demonstration of performing the above-explained basic graph theory operations using Python. We have used NetworkX library, which has been developed for easy creation, manipulation and analysis of complex networks and graph structures. The code below has been implemented using Python 3.7.10 and networkx 2.5.1 versions. Step-wise implementation of the code is as follows:

  1. Install NetworkX library.

!pip install networkx

  1. Import required libraries.
 import networkx as ntwkx
 import matplotlib.pyplot as plt 
  1. Instantiate Graph instance

G1 = ntwkx.Graph()

  1. Add edges to the graph using add_edges_from() method. The edges are specified as 2-tuple (x,y), which means an edge is to be drawn joining vertices x and while or a 3-tuple (x,y,d) where d is a dictionary containing the edge’s data.
G1.add_edges_from([(1, 3), (2, 3), (3, 4), (1, 5), (2, 4), (4, 5), (5, 6), (6, 7), (5, 8),(7, 8)])
  1. Plot the created graph.
 #Title of the plot
 plt.suptitle("Original graph")
 #draw_networkx() method draws the graph G1 using matplotlib 


  1. Create a subgraph from the above graph G1.

SG1 = G1.subgraph([1, 3, 4, 5])

Plot the subgraph

 #Title of the plot
 plt.suptitle("Subgraph of G1")
 #Draw the subgraph using matplotlib


  1. Union of two graphs

Create 1st graph named G2

 #Instantite a Graph object
 G2 = ntwkx.Graph()
 #Add edges to the grap
 G2.add_edges_from([(1, 2), (1, 3), (2, 3), (2, 4), (2, 5), (3, 4), 
                          (4, 5), (4, 6), (5, 7), (5, 8), (7, 8)])
 # Draw graph G2 using matplotlib


union graph 1

Create 2nd graph named G3

 G3 = ntwkx.Graph()
 G3.add_edges_from([(13, 14), (13, 15), (13, 9),
                   (14, 15), (15, 10), (9, 10)])
 # Second Graph created
 plt.suptitle("Graph G3")


union graph 2

Create union of G2 and G3

 #G2 and G3 must be disjoint graphs else union() method raises error
 U = ntwkx.union(G2, G3)
 #Title of the plot
 plt.suptitle("Union of G2 and G3")
 #Draw the union graph using matplotlib


union graph
  1. Composition of graphs

compose() method simply performs the same task as union() if the graphs have no node in common. If the graphs have common nodes, they create a connected graph withboth the constituent graphs as subgraphs.

For graphs having no common node:

 C1 = ntwkx.compose(G2,G3)
 #Title of the plot
 plt.suptitle("Composition of disjoint graphs")
#Draw the composed graph


For graphs having common nodes:

 #Create 1st graph
 G4 = ntwkx.Graph()
 G4.add_edges_from([(1, 2), (1, 3), (2, 3), (2, 4)])
 plt.suptitle("Graph G4")


 #Create 2nd graph
 G5 = ntwkx.Graph()
 G5.add_edges_from([(3, 7), (7, 4), (3, 4)])
 # Second Graph created
 plt.suptitle("Graph G5")


Composition of graphs G4 and G5:

 C2 = ntwkx.compose(G4, G5)
 plt.suptitle("Composition with common node")


composition of graph
  1. Complement of a graph
 #Display graph G4
 plt.suptitle(“Graph G4”)


#Complement of graph G4

 comp = ntwkx.complement(G4)
 plt.suptitle("Complement of graph G4")


complement of graph

More Great AIM Stories

Nikita Shiledarbaxi
A zealous learner aspiring to advance in the domain of AI/ML. Eager to grasp emerging techniques to get insights from data and hence explore realistic Data Science applications as well.

Our Upcoming Events

Masterclass, Virtual
How to achieve real-time AI inference on your CPU
7th Jul

Masterclass, Virtual
How to power applications for the data-driven economy
20th Jul

Conference, in-person (Bangalore)
Cypher 2022
21-23rd Sep

Conference, Virtual
Deep Learning DevCon 2022
29th Oct

3 Ways to Join our Community

Discord Server

Stay Connected with a larger ecosystem of data science and ML Professionals

Telegram Channel

Discover special offers, top stories, upcoming events, and more.

Subscribe to our newsletter

Get the latest updates from AIM

What can SEBI learn from casinos?

It is said that casino AI technology comes with superior risk management systems compared to traditional data analytics that regulators are currently using.