PGDDSA Study · Semester 1

PGD01C01

Module 2 · Graph Theory

Graphs: Definition and Types

Core Titles

Key headlines and terms for quick recall

Graph $G = (V, E)$
Simple graph, Multigraph, Pseudograph
Directed (digraph) vs Undirected
Complete graph $K_n$ — every pair joined
Bipartite $K_{m,n}$
Regular graph — all vertices same degree
Subgraph, Spanning subgraph
Degree $\deg(v)$ ; Handshaking lemma

Basic Idea

What it is, why it matters, how it works

What is a graph?

A graph $G = (V, E)$ is a pair where $V$ is a set of vertices and $E$ is a set of edges connecting them. Graphs model anything pairwise — networks, maps, social ties.

Common types

Simple graph — no self-loops, no multi-edges.
Multigraph — multiple edges allowed between the same pair.
Pseudograph — multi-edges and self-loops allowed.
Directed graph (digraph) — edges have direction (arrows).
Weighted graph — edges carry numeric weights.

Special graphs

Complete graph $K_n$ : every pair of $n$ vertices connected. Has $\binom{n}{2}$ edges.
Bipartite graph: $V = V_1 \cup V_2$ , edges only between $V_1$ and $V_2$ .
Complete bipartite $K_{m,n}$ : $mn$ edges.
Regular graph: every vertex has the same degree $k$ .
Null graph: no edges.

Degree and handshaking

The degree of vertex $v$ , $\deg(v)$ , is the number of edges incident to it (self-loops count twice).

Handshaking lemma. $\displaystyle \sum_{v \in V} \deg(v) = 2|E|$ .

Corollary: The number of odd-degree vertices is always even.

Why this matters in Data Science

Knowledge graphs, recommendation systems, transportation networks, NLP dependency parses, neural-network computation graphs.

Mind Map

Visual structure of the concept

GRAPH G = (V, E)
├── Types
│   ├── Simple
│   ├── Multigraph
│   ├── Pseudograph (loops + multi-edges)
│   ├── Directed (digraph)
│   └── Weighted
├── Special graphs
│   ├── Complete Kₙ            (|E| = nC2)
│   ├── Bipartite Kₘ,ₙ         (|E| = mn)
│   ├── Regular (all deg = k)
│   └── Null (no edges)
└── Degree & Handshaking
    ├── deg(v)
    ├── Σ deg(v) = 2|E|
    └── # odd-degree vertices is even

Exam Q&A

Part A (2 marks) and Part B (20 marks) style questions

Part A (2 marks each)

Q1. Define a simple graph. A graph with no self-loops and no multiple edges between the same pair of vertices.

Q2. How many edges in $K_n$ ? $\binom{n}{2} = \dfrac{n(n-1)}{2}$ .

Q3. State the handshaking lemma. $\sum_{v} \deg(v) = 2|E|$ .

Q4. Define a bipartite graph. A graph whose vertex set partitions into two disjoint sets $V_1, V_2$ such that every edge connects $V_1$ to $V_2$ .

Part B (20 marks)

Q. Define different types of graphs with examples. State and prove the handshaking lemma. Use it to show that in any graph the number of vertices of odd degree is even.

Definitions with examples.

Simple graph — no loops, no parallel edges. A road map between cities (one road per pair).
Multigraph — parallel edges allowed. Multiple flights between two airports.
Pseudograph — loops and multi-edges allowed.
Directed graph — edges with direction. A Twitter "follow" network.
Complete graph $K_n$ — every pair connected. $K_4$ has 6 edges.
Bipartite graph $K_{m,n}$ — vertices split into two parts with edges only between. A student–course enrolment graph.
Regular graph — every vertex same degree.

Handshaking lemma. In any undirected graph $G = (V, E)$ , $\sum_{v \in V} \deg(v) = 2|E|.$

Proof. Each edge $\{u, v\}$ contributes exactly 1 to $\deg(u)$ and 1 to $\deg(v)$ — i.e., 2 to the total sum. Summing over all $|E|$ edges gives $2|E|$ . ∎

Corollary — odd-degree count is even. Split $V$ into odd-degree set $V_O$ and even-degree set $V_E$ . Then $\sum_{v \in V_O} \deg(v) + \sum_{v \in V_E} \deg(v) = 2|E|.$ The second sum is even (sum of evens). $2|E|$ is even. So $\sum_{V_O} \deg(v)$ is even. But it's a sum of odd numbers — that can be even only when the count $|V_O|$ is even. ∎

Permutations and Combinations Paths, Circuits, Eulerian and Hamiltonian Circuits