Graph Theory Basics: Definitions, Models, Paths & Connectivity

What is a Graph?

A graph $G$ is a pair $(V,E)$, where:

• $V$ is a non-empty finite set of vertices (also called nodes).
• $E$ is a set of edges connecting pairs of vertices.

Types of Graphs

Graphs can be classified based on their properties:

Visualizing Graphs

Graphs are best understood visually. Here’s a simple undirected graph with 5 vertices and 6 edges:

graph TD
    A["Vertex 1"] -- 3 --> B["Vertex 2"]
    A -- 1 --> C["Vertex 3"]
    B -- 2 --> C
    B -- 4 --> D["Vertex 4"]
    C -- 5 --> D
    D -- 6 --> E["Vertex 5"]

Key Terms:

• Degree of a vertex ($\mathrm{deg}(v)$): Number of edges incident to it.
  • In undirected graphs: $\mathrm{deg}(A)=2$, $\mathrm{deg}(B)=3$, etc.
  • In directed graphs: In-degree (edges coming in) and Out-degree (edges going out).
• Isolated vertex: A vertex with no edges (e.g., if $F$ were added with no connections).
• Adjacent vertices: Vertices connected by an edge (e.g., $A$ and $B$ are adjacent).

Graph Representations

Graphs can be stored in memory or on paper using two primary methods:

1. Adjacency Matrix

A square matrix $A$ of size $|V|\times |V|$, where:

• $A[i][j]=1$ if there is an edge from vertex $i$ to $j$, else $0$.
• For weighted graphs, store the weight instead of 1.
• For directed graphs, $A[i][j]$ may not equal $A[j][i]$.

Example (Undirected Graph Above):

      A   B   C   D   E
   ----------------
A | 0   1   1   0   0
B | 1   0   1   1   0
C | 1   1   0   1   0
D | 0   1   1   0   1
E | 0   0   0   1   0

Pros and Cons:

2. Adjacency List

A list of lists, where each vertex maps to its adjacent vertices (and optionally edge weights).

Example (Undirected Graph Above):

A: [B, C]
B: [A, C, D]
C: [A, B, D]
D: [B, C, E]
E: [D]

Pros and Cons:

Paths, Cycles, and Connectivity

Paths

A path is a sequence of vertices where each adjacent pair is connected by an edge.

• Simple path: No repeated vertices.
• Closed path (Cycle): Ends at the starting vertex.

Example (Simple Path in the Graph Above): $A\to B\to D\to E$

Worked Example: Counting Paths How many simple paths exist from $A$ to $E$ in the graph above? Solution:

1. $A\to B\to D\to E$
2. $A\to C\to D\to E$ Total paths = 2.

Cycles

A cycle is a path that starts and ends at the same vertex with no repeated edges (except the first/last).

• Hamiltonian Cycle: Visits every vertex exactly once.
• Eulerian Cycle: Uses every edge exactly once.

Example (Cycle in the Graph Above): $B\to C\to D\to B$

Connectivity

A graph is connected if there is a path between every pair of vertices.

• Connected Component: A maximal connected subgraph.
• Strongly Connected (Directed Graph): Every vertex is reachable from every other vertex.

Worked Example: Checking Connectivity Is the graph above connected? Solution:

• Start at $A$: Can reach $B,C,D,E$.
• Start at $E$: Can reach $D$, then $B,C$, and finally $A$. Conclusion: Yes, the graph is connected.

In the Real World

Graph theory is everywhere in technology and daily life. Here’s how companies and apps in Nepal and globally use these ideas:

1. Pathao (Ride-Hailing App)

   • Idea Used: Shortest Path Problem (Graph Traversal)
   • How? Pathao’s algorithm treats cities as vertices and roads as edges (with weights = travel time/distance). When you request a ride, the app uses Dijkstra’s algorithm (a graph traversal technique) to find the fastest route from your location to the driver’s location, avoiding traffic jams (represented as higher edge weights).
   • Real Example: If you order a ride from Thapathali to Lakshmi Narayan Chowk, Pathao’s backend calculates the optimal path by evaluating all possible routes (e.g., via Ring Road vs. via Putalisadak) and picks the one with the least estimated time.

2. NTC (Nepal Telecommunications Corporation) Network

   • Idea Used: Minimum Spanning Tree (MST)
   • How? NTC’s fiber-optic cable network across Nepal must connect all major cities (vertices) with the least total cable length (edge weights = distance). They use Kruskal’s or Prim’s algorithm to design the most cost-effective network without redundant connections.
   • Real Example: When expanding 4G coverage to remote districts like Dolpa or Mugu, NTC first models the region as a graph, then applies MST to determine the shortest cable routes from existing towers in Jumla or Surkhet.

3. eSewa (Digital Payment Platform)

   • Idea Used: Bipartite Graphs (Matching Problem)
   • How? eSewa’s backend uses graph theory to match transactions between users and service providers (e.g., electricity bills, SIM top-ups). The system models users and providers as two disjoint sets of vertices, with edges representing valid transactions. Algorithms like Hopcroft-Karp find the maximum matching to ensure seamless payments.
   • Real Example: When you pay your Ncell bill via eSewa, the platform checks if your account (vertex in Set A) can be matched to Ncell’s billing system (vertex in Set B) without conflicts, using bipartite graph matching.

4. Khalti (Digital Wallet)

   • Idea Used: Graph Coloring (Conflict Resolution)
   • How? Khalti uses graph coloring to schedule transactions and fraud detection. Each transaction is a vertex, and conflicts (e.g., double-spending attempts) are edges. Coloring the graph ensures no two conflicting transactions share the same "time slot" for processing.
   • Real Example: If two users in Kathmandu try to transfer money to the same merchant’s account simultaneously, Khalti’s system colors their transactions differently to avoid processing them in the same batch, preventing errors.

5. Nepal Electricity Authority (NEA) Power Grid

   • Idea Used: Flow Networks (Max Flow Problem)
   • How? NEA’s power distribution network is modeled as a flow network where vertices are substations and edges are power lines with capacity limits. The Ford-Fulkerson algorithm helps determine the maximum power that can be supplied from generation plants (e.g., West Seti) to demand centers (e.g., Kathmandu) without overloading any line.
   • Real Example: During peak hours (e.g., winter evenings), NEA uses max flow algorithms to reroute excess power from Butwal to Pokhara if the direct line to Kathmandu is saturated.

Graph Traversal Algorithms (Preview)

While not covered in detail here, two foundational algorithms are worth mentioning for their real-world applications:

1. Breadth-First Search (BFS)

• Idea: Explores all vertices at the present depth before moving deeper.
• Use Case: Shortest path in unweighted graphs (e.g., Pathao’s initial route estimation).
• Example Trace: Start at $A$, visit neighbors $B,C$, then $D,E$, etc.

2. Depth-First Search (DFS)

• Idea: Explores as far as possible along a branch before backtracking.
• Use Case: Topological sorting (e.g., task dependencies in project management).
• Example Trace: $A\to B\to D\to E\to C$.

Exam Tip

Graph theory questions in TU exams typically test:

1. Definitions: Be precise with terms like degree, path, cycle, and connectivity. For example:
   • "Define a simple graph and give an example." → Answer: "A graph with no loops or multiple edges between the same pair of vertices. Example: A friendship network where each person is a vertex and each friendship is an edge."
2. Graph Representations: Expect questions on converting between adjacency matrices/lists. For example:
   • "Convert the following adjacency matrix to an adjacency list."
   • "Given an adjacency list, draw the graph and find the degree of vertex 3."
3. Path/Cycle Counting: Practice counting simple paths or identifying cycles in small graphs (4–6 vertices). Always draw the graph first!
4. Real-World Applications: Link theoretical concepts to practical scenarios. For example:
   • "How would you model Kathmandu’s traffic routes as a graph? What algorithm would you use to find the fastest route from Thamel to Narayanhiti Palace?"
5. Proofs: For connectivity or degree-sum problems, use the Handshaking Lemma ($\sum \mathrm{deg}(v)=2|E|$) or induction.

Common Pitfalls:

• Forgetting to distinguish between directed and undirected graphs (e.g., confusing in-degree/out-degree).
• Misapplying adjacency matrix/list for weighted graphs (e.g., storing weights as booleans).
• Overlooking isolated vertices or loops in proofs.

High-Score Strategy:

• Draw the graph: Even for theoretical questions, sketching helps visualize relationships.
• Label everything: In proofs, explicitly state which vertices/edges you’re referring to.
• Use examples: If asked to prove a property (e.g., "A graph with all vertices of even degree is Eulerian"), start with a small example (e.g., a square) before generalizing.

Worked Example: Modeling Kathmandu Traffic Routes

Question: Model the following Kathmandu routes as a graph and find the shortest path from Thamel (A) to Kantipath (E) using unweighted edges. Assume the roads are:

• Thamel (A) → Asan (B), Thamel (A) → Durbar Square (C)
• Asan (B) → Durbar Square (C), Asan (B) → Kantipath (E)
• Durbar Square (C) → Kantipath (E)
• Kantipath (E) → Garden of Dreams (F)

Solution:

1. Graph Representation:

2. Shortest Path (BFS):
   • Start at $A$, explore neighbors $B$ and $C$.
   • From $B$, reach $E$ directly (path: $A\to B\to E$).
   • From $C$, also reach $E$ (path: $A\to C\to E$).
   • Both paths have length 2, so either is the shortest.

Real-World Tie-In: This mirrors how Pathao or Google Maps initially estimate routes by treating roads as unweighted edges. Later, they refine the path by adding weights (traffic data, road conditions) and applying Dijkstra’s algorithm.