Graph Theory with Practicals is a comprehensive and student-friendly resource designed to introduce learners to the fundamental and advanced concepts of graph theory, an essential area in mathematics and computer science. The book emphasizes the application of graph-based thinking in solving real-world problems related to networks, algorithms, and data structures.
The text begins with basic concepts such as vertices, edges, paths, and different types of graphs, gradually progressing to important topics like graph operations, matrix representations, connectivity, and traversability. Key concepts including Eulerian and Hamiltonian paths, as well as practical problem-solving approaches like the Travelling Salesman Problem, are explained in a clear and systematic manner.
The book also covers essential graph algorithms such as Dijkstra’s and Bellman–Ford algorithms, along with traversal techniques like Breadth-First Search (BFS) and Depth-First Search (DFS). A dedicated section on trees explores their properties, types, and applications, including spanning trees and search trees.
With a strong focus on practical learning, the book includes numerous solved examples, exercises, and hands-on problems that help students apply theoretical concepts effectively. Written in simple language and well-structured format, this book serves as an ideal guide for building analytical skills and mastering graph theory for academic and professional purposes.
CA 215(B) : Graph Theory
1. Introduction to Graph Theory
1.1 Graph
1.2 Edge
1.2.1 Types of edges
1.3 Vertex
1.4 Loop or Self loop:
1.5 Degree of a vertex
1.6 Hand Shaking Theorem
1.7 Solved Examples
1.8 Finite graph
1.9 Infinite graph
1.10 Order and size of graph
1.11 Incidency and Adjacency
1.12 Parallel or multiple edges
1.13 Isolated vertex
1.14 Pendant Vertex
1.15 In-degree and out-degree
1.16 Even and Odd Vertices
1.17 Path
1.18 Null Graph
1.19 Simple graph
1.20 Types of Graph
1.20.1 Complete graph
1.20.2 Regular graph
1.20.3 Directed graph
1.20.4 Petersen graph
1.20.5 Mixed graph
1.21 Operation on graphs
1.22 Deletion of Vertex
1.23 Deletion of Edge
1.24 Fusion of two vertices
1.25 Product of graph
1.26 Matrix Representation of graph
1.27 Solved Examples
1.28 Incidence matrix of Digraph
1.29 Adjacency matrix of a non-directed graph
1.30 Adjacency Matrix of a Directed Graph
2. Graph Connectivity and Traversability
2.1 Connectivity
2.2 Cut Vertices and Cut Edges
2.3 Blocks
2.4 Traversability
2.4.1 Eulerian paths and Circuits
2.5 Terminal Vertices
2.6 Open Walk
2.7 Closed Walk
2.8 Eulerian Walk or Euler line
2.9 Solved Examples
2.10 Travelling - Salesman Problem
3. Graph Algorithm
3.1 Shortest Paths Algorithm
3.2 Dijkstra's Algorithm to find Shortest Paths from a Source to all
3.3 Bellman–Ford Algorithm
3.4 Graph Traversal Techniques
3.5 Breadth- First Search (BFS)
3.6 Depth first Search (DFS) Algorithm
3.7 Applications of BFS in Graphs
3.8 Applications of Depth First Search
4. Trees
4.1 Trees
4.2 Properties of tree
4.3 Minimally connected graph
4.4 Trivial tree
4.5 Non-trivial tree
4.6 Types of tree
4.7 Eccentricity
4.8 Fundamental circuit
4.9 Cut sets and cut vertices
4.10 Fundamental cut-set
4.11 Weight of a spanning tree
4.12 Edge Connectivity
4.13 Vertex Connectivity
4.14 Separable graph
4.15 Cut - vertex or cut-point
4.16 Application of tree
4.16.1 Kruskal’s Algorithm
4.17 Prim’s Algorithm
4.18 Binary Search Tree (BST)
4.19 Decision Tree
CA-216(B) : Practical on Graph Theory.
1. Graph: A simple undirected graph with 6 vertices A,B,C,D,E, F, and edges: AB,AC,BD,CD,DE,EF.
2. Graph: A directed graph with 5 vertices P,Q,R,S,T and directed edges: PQ,QR,RS,ST,TP.
3. Graph G1: Vertices A, B,C and edges AB,BC. Graph G2: Vertices X,Y,Z and edges XY,YZ.
4. Graph: A weighted undirected graph with vertices V1,V2,V3,V4 and edges V1V2=2,V2V3=3,V3V4=4,V1V4=5. Represent this graph using an adjacency matrix.
5. Graph: An undirected graph with 8 vertices and edges connecting some vertices to form two disjoint sub-graphs.
6. Graph: A graph forming a square ABCD with diagonals AC and BD.
7. Graph: A directed weighted graph with vertices A, B, C, D, E and edges with weights
8. Graph: A tree with vertices A, B, C, D, E, F, where A is the root, A→B, A→C, B→D, B→E, C→F
BCA(Honors/Research) SecondYear, Semester – III, CA 215-216(B) Thistextbook is aligned with the revised syllabus as outlined by the NationalEducation Policy 2020 (NEP 2020) for the Faculty of Science and TechnologyFaculty at K.B.C. North Maharashtra University, Jalgaon, effective from June2025.
