Introduction to Graph Theory

Name: Introduction to Graph Theory
Rating: 4.5 (2 reviews)

Graphs and its apllications

Created byDr. Divya Jain

Last updated 1/2026

English

English [Auto],

What you'll learn

Understand and explain fundamental concepts of graph theory including types of graphs, graph representations, and basic terminology.
Analyze properties of graphs such as degree, connectivity, paths, cycles, and trees.
Apply graph traversal techniques and spanning tree concepts to solve engineering problems.
Solve optimization problems using shortest path and network flow algorithms.

Course content

5 sections • 14 lectures • 1h 31m total length

Why Graph Theory7:26
Reveals graph theory as the hidden language of connectivity powering the internet, maps, and social networks, enabling artificial intelligence, optimization, and algorithmic thinking.

Introduction6:16
Define graphs as vertex sets connected by edges, compare directed and undirected types, and summarize degree, adjacent, isolated, pendant vertices, spanning subgraphs, and in-degree and out-degree with real-world examples.
Vertices7:42
Explore vertex types including root, internal, cut, and sink in directed and undirected graphs, along with edge types like directed, undirected, self-loops, multiple edges, and weights.
Degree of Region4:03
Types of Edges7:17
Explore directed and undirected edges, self-loops, multiple and weighted edges, and classify graphs as undirected, directed, simple, multigraph, pseudograph, and directed multigraph.

Types and properties of Graphs5:25
Explore the types and properties of graphs, including complete graphs, cycles, wheels, cubes, bipartite and complete bipartite graphs, and regular graphs, with definitions, examples, and degree and edge counts.
Isomerphism of Graphs7:12
Explore graph isomorphism via a bijective mapping that preserves adjacency and degrees, and see how the seven bridges of Konigsberg illustrate Eulerian graphs with all vertices of even degree.
Distance in a Graph7:44
Explore distance in a graph through shortest paths, eccentricity, radius, and diameter, then distinguish walks, trails, paths, circuits, and cycles with clear examples.
Hamiltonian Graphs4:15
Explore hamiltonian graphs and hamiltonian cycles, where each vertex is visited once, and how Dirac's and Ore's theorems guarantee hamiltonian circuits, with traveling salesman implications.

Advance concepts and Applications of Graphs5:32
Explore advanced graph theory concepts like connectivity, counting path, path matrix, dual graphs and regions, graph colouring and chromatic number, and analyze articulation points and connectivity types in directed graphs.
Coloring of Graph10:29
Color graphs by assigning colors to vertices so adjacent vertices differ and determine the chromatic number—the minimum colors needed. Apply to exam timetable scheduling and use Welch-Powell for efficient coloring.

Trees10:07
Explore trees in graph theory: connected acyclic graphs with a unique path between vertices, rooted trees, and concepts such as root, parent, child, levels, height, and binary and m-ary variants.
Trees (Contd)4:20
Explore balanced rooted binary trees with leaves at levels 3 or 4 and their height. Learn preorder, inorder, and postorder traversals through a single example tree.
Minimum Spanning Trees3:59
Learn how minimum spanning trees connect all vertices with minimum edge weight in a weighted graph, using Prim's and Kruskal's algorithms, while avoiding cycles.

Requirements

sets and relations

Description

Graph Theory is a fundamental course in discrete mathematics that provides the theoretical foundation for understanding and analyzing structures consisting of objects and the relationships between them. This course introduces graphs as powerful mathematical models used to represent real-world systems such as computer networks, communication systems, transportation networks, social networks, and scheduling problems. The course begins with basic concepts including definitions of graphs, types of graphs, graph representations, and graph isomorphism, enabling students to develop a strong conceptual base.

The course further explores important properties of graphs such as degree of vertices, paths, cycles, connectivity, and components. Special classes of graphs including trees, bipartite graphs, complete graphs, and planar graphs are studied in detail, along with their structural characteristics and applications. Emphasis is placed on trees and spanning trees due to their extensive use in network design and optimization.

Students are introduced to fundamental graph algorithms such as graph traversal techniques (Breadth First Search and Depth First Search), shortest path algorithms, and minimum spanning tree algorithms. The course also covers Eulerian and Hamiltonian graphs, graph coloring, and matching, which are essential for solving problems related to routing, resource allocation, timetabling, and circuit design.

Throughout the course, theoretical concepts are reinforced with problem-solving and real-life applications, enabling students to analyze and model complex engineering problems effectively. By the end of the course, students will be equipped with the analytical and computational skills necessary for advanced studies in algorithms, data structures, optimization techniques, and network analysis, making Graph Theory an essential component of engineering and computer science education.

Who this course is for:

CSE Students

Introduction to Graph Theory

What you'll learn

Explore related topics

Course content

Why Graph Theory?1 lecture • 7min

Introduction of Graph4 lectures • 25min

Types and Properties of Graphs4 lectures • 25min

Advance concepts and Applications of Graphs2 lectures • 16min

Trees (Graph)3 lectures • 18min

Requirements

Description

Who this course is for: