Engineering Fluency OS

Why This Matters

The internet is a graph. Social networks are graphs. Road maps, dependency trees, circuit boards, and even the structure of this course are all graphs. A vertex represents an entity — a person, a city, a web page — and a edge represents a connection between two entities. The concept of adjacency tells us which vertices are directly connected.

Graph theory gives computer science its most versatile data structure. Shortest path algorithms power GPS navigation. PageRank (which launched Google) analyzes the web graph. Social media friend suggestions, package dependency resolution, compiler optimizations, and network routing all reduce to graph problems. If you understand vertices, edges, and adjacency, you can model almost any relationship in the real world.

Define Terms

Visual Model

Vertex ANode / Point

Vertex BNode / Point

Vertex CNode / Point

Vertex DNode / Point

Adjacency ListA:[B,C] B:[A,D] C:[A,D] D:[B,C]

Degreedeg(A)=2 deg(B)=2 deg(C)=2 deg(D)=2

The full process at a glance. Click Start tour to walk through each step.

A graph with 4 vertices and 4 edges. The adjacency list encodes who is connected to whom.

Code Example

Code

// Build an undirected graph using an adjacency list
class Graph {
  constructor() {
    this.adjList = new Map();
  }

  addVertex(v) {
    if (!this.adjList.has(v)) {
      this.adjList.set(v, []);
    }
  }

  addEdge(v1, v2) {
    this.addVertex(v1);
    this.addVertex(v2);
    this.adjList.get(v1).push(v2);
    this.adjList.get(v2).push(v1);
  }

  degree(v) {
    return this.adjList.get(v)?.length || 0;
  }

  neighbors(v) {
    return this.adjList.get(v) || [];
  }

  printGraph() {
    for (const [vertex, neighbors] of this.adjList) {
      console.log(`${vertex}: [${neighbors.join(", ")}]`);
    }
  }
}

const g = new Graph();
g.addEdge("A", "B");
g.addEdge("A", "C");
g.addEdge("B", "D");
g.addEdge("C", "D");

g.printGraph();
// A: [B, C]
// B: [A, D]
// C: [A, D]
// D: [B, C]

console.log("Degree of A:", g.degree("A")); // 2
console.log("Neighbors of B:", g.neighbors("B")); // [A, D]

// Verify Handshaking Lemma: sum of degrees = 2 * edges
let totalDegree = 0;
for (const [v] of g.adjList) {
  totalDegree += g.degree(v);
}
console.log("Sum of degrees:", totalDegree); // 8 = 2 * 4 edges

Interactive Experiment

Try these exercises:

Build a graph of 5 cities connected by roads. Print the adjacency list and verify each vertex degree.
Add a vertex with no edges (an isolated vertex). What is its degree?
Create a complete graph on 4 vertices (every pair connected). How many edges does it have? What is each degree?
Try creating a directed graph by only adding one direction per edge. How does the adjacency list change?
Can you build a graph where the degrees are 1, 2, 3, 4, 5? Why or why not? (Hint: Handshaking Lemma.)

Quick Quiz

Coding Challenge

Build Adjacency List and Compute Degrees

Write a function called `buildGraph` that takes an array of edges (each edge is a two-element array like [v1, v2]) and returns an object with two properties: `adjList` (an object mapping each vertex to its array of neighbors) and `degrees` (an object mapping each vertex to its degree). The graph is undirected, so each edge appears in both directions.

Loading editor...

Real-World Usage

Graph theory is one of the most applied areas of mathematics in computing:

Social networks: Facebook, Twitter, and LinkedIn model users as vertices and relationships as edges. Friend suggestions use graph traversal to find friends-of-friends.
Web search: Google PageRank treats the web as a directed graph where pages are vertices and hyperlinks are edges. A page linked by many important pages ranks higher.
GPS navigation: Road networks are weighted graphs. Dijkstra and A* algorithms find shortest paths for turn-by-turn directions.
Package managers: npm, pip, and cargo model dependencies as directed acyclic graphs. Topological sort determines installation order.
Network routing: Internet routers use graph algorithms (OSPF, BGP) to find efficient paths for data packets.

Graph Theory