Skip to content
Home » Graph Theory

Graph Theory

Here is a clear, simple, and exam-oriented introduction to Graph Theory — perfect for BCA/MCA/Engineering/Discrete Mathematics.

⭐ Introduction to Graph Theory

Graph Theory is a branch of discrete mathematics that studies relationships between objects.
A graph is a mathematical structure used to model pairwise connections.

Graphs are used extensively in:

✔ Computer Science
✔ Networking
✔ Social Networks
✔ Transportation
✔ AI & Machine Learning
✔ Operations Research
✔ Chemistry, Biology, Physics

Graph Theory helps represent and analyze connections, paths, networks, and structures.

⭐ 1. What Is a Graph?

A graph (G) consists of:

[
G = (V, E)
]

Where:

  • V = set of vertices (nodes)
  • E = set of edges (connections between vertices)

Example:

Vertices: {A, B, C}
Edges: {(A,B), (B,C)}

⭐ 2. Types of Graphs

✔ 1️⃣ Undirected Graph

Edges have no direction.
(A, B) = (B, A)

Used in:

  • Social networks
  • Electrical networks

✔ 2️⃣ Directed Graph (Digraph)

Edges have direction.
⟨A, B⟩ ≠ ⟨B, A⟩

Used in:

  • Web links
  • Precedence constraints
  • Road networks

✔ 3️⃣ Weighted Graph

Edges have weights (cost, time, distance).

Used in:

  • Dijkstra’s shortest path algorithm
  • Traffic routing
  • Network optimization

✔ 4️⃣ Simple Graph

No loops, no parallel edges.

✔ 5️⃣ Multigraph

Allows parallel edges.

✔ 6️⃣ Complete Graph (Kn)

Every pair of vertices is connected by an edge.

Number of edges:
[
\frac{n(n-1)}{2}
]

✔ 7️⃣ Bipartite Graph

Vertices can be divided into two sets such that no edges connect vertices in the same set.

Used in:

  • Matching problems
  • Job assignment
  • Recommendation systems

✔ 8️⃣ Tree

A connected graph with no cycles.

Properties:

  • If n vertices, then n−1 edges
  • Unique path between any two vertices

Trees are used in:

  • Data structures (Binary trees, AVL, B-trees)
  • File systems
  • Networks

⭐ 3. Basic Terminology

✔ Degree of a vertex

Number of edges incident to a vertex.

✔ Path

A sequence of vertices connected by edges.

✔ Cycle

A path where first and last vertices are the same.

✔ Connected graph

There is a path between every pair of vertices.

✔ Component

A maximally connected subgraph.

✔ Subgraph

A smaller graph inside a big graph.

⭐ 4. Special Structures

✔ Euler Path & Circuit

Covers each edge once.

Conditions:

  • Euler circuit: all vertices have even degree
  • Euler path: exactly 0 or 2 vertices have odd degree

✔ Hamiltonian Path & Circuit

Visits each vertex once.

Applications:

  • Traveling Salesman Problem (TSP)

⭐ 5. Applications of Graph Theory

✔ Computer Networks

Routers, switches, internet connections modeled as graphs.

✔ Artificial Intelligence

Graph search (A*, BFS, DFS)

✔ Social Networks

Facebook, LinkedIn → Nodes = people; Edges = connections

✔ Transport & Routing

Shortest path algorithms.

✔ Compiler Design

Control flow graphs.

✔ Databases

Dependency graphs, ER diagrams.

✔ Image Processing

Pixel connections, object edges.

✔ Operations Research

Scheduling, matching, flow networks.

✔ Cryptography

Graph-based public key systems.

⭐ 6. Advantages of Using Graphs

✔ Represent complex relationships
✔ Easy to visualize connections
✔ Algorithms available for shortest paths, spanning trees, flows
✔ Suitable for discrete & network data
✔ Used in real-world systems

⭐ Quick Exam Summary

Graph (G):

[
G = (V, E)
]

Types of Graphs:

  • Undirected
  • Directed
  • Weighted
  • Simple
  • Complete
  • Bipartite
  • Tree

Important Concepts:

  • Degree
  • Path
  • Cycle
  • Connectedness
  • Subgraph
  • Components

Applications:

Routing, AI, networks, DBMS, scheduling, social networks, TSP, etc.