Graph Foundations

Core Concepts

Vertices and Edges

A graph is a mathematical structure consisting of two things: a set of vertices (also called nodes) and a set of edges that connect pairs of vertices. Vertices represent objects or entities. Edges represent relationships or connections between those objects.

That is the entire primitive. Everything in graph theory — algorithms, proofs, applications — is built on top of it.

In notation, a graph is usually written as G = (V, E) where V is the vertex set and E is the edge set.

Undirected Graphs

In an undirected graph, edges have no direction. If there is an edge between vertices A and B, the relationship is symmetric: traversal from A to B and from B to A are equally valid. There is no "from" and "to" — just "between."

The adjacency matrix of an undirected graph is always symmetric: the entry at position (i, j) equals the entry at position (j, i).

Real-world examples: a road map where all roads are two-way; a friendship network where "A is friends with B" implies "B is friends with A."

Directed Graphs (Digraphs)

A directed graph — or digraph — is a graph in which each edge has a specified direction. The formal definition shifts slightly: G = (V, A), where A is a set of ordered pairs of vertices called arcs or directed edges. The ordering matters: the arc (A, B) is not the same as the arc (B, A).

Directed edges model asymmetric relationships.

Real-world examples: web pages and hyperlinks (page A can link to B without B linking back); a task dependency graph (task A must complete before task B starts); Twitter follows.

Fig 1

Weighted Graphs

A weighted graph assigns a numerical value — the weight — to each edge. Weights can represent cost, distance, latency, capacity, or any quantity relevant to the application. Weighted graphs can be either directed or undirected.

When computing the total weight of a path, you sum the weights of its constituent edges.

When weights are meaningful: whenever the edges are not equivalent. A road network where travel time varies by route; a network topology where links have different bandwidths; a cost graph for resource allocation. When all edges are equivalent, an unweighted graph is simpler and sufficient.

Simple Graphs vs. Multigraphs

These two concepts define what is allowed between any pair of vertices.

A simple graph contains no multiple edges and no self-loops. Between any two distinct vertices, there is at most one edge. A vertex cannot have an edge back to itself.

A multigraph permits multiple edges (parallel edges) between the same pair of vertices, and may also permit self-loops. Two cities connected by three different flight routes is a multigraph scenario. The same pair of vertices simply appears more than once in the edge set.

Complete Graphs

A complete graph is a simple undirected graph where every pair of distinct vertices is connected by exactly one edge. A complete graph on n vertices is denoted K_n.

Two properties follow immediately:

• Every vertex in K_n has degree n − 1 (it is adjacent to every other vertex).
• The total number of edges in K_n is n(n − 1) / 2.

K_n is the densest possible simple graph. It is also maximally robust: at least n − 1 edges must be removed to disconnect it.

Vertex Degree

The degree of a vertex is the number of edges incident to it — the count of its direct connections.

In undirected graphs, degree is a single count. A vertex with degree 0 is isolated. A vertex with degree 1 is a leaf.

In directed graphs, degree splits into two:

• In-degree: the number of edges arriving at the vertex (incoming arcs).
• Out-degree: the number of edges leaving the vertex (outgoing arcs).

A vertex with high in-degree has many things pointing to it — an authority signal in networks like the web. A vertex with high out-degree points to many things — a hub or broadcaster.

Adjacency

Two vertices are adjacent if they are connected by an edge. The set of all vertices adjacent to a given vertex v is called its neighborhood — often written N(v).

Adjacency is the most local structural property a graph has. Most traversal algorithms (BFS, DFS) operate by iterating over neighbors: given where you are, what vertices can you reach in one step?

Graph Isomorphism

Two graphs are isomorphic if there exists a one-to-one mapping (bijection) between their vertex sets that preserves all adjacency relationships. Informally: if you can relabel the vertices of one graph to produce the other, the two graphs are isomorphic — they are structurally the same graph wearing different names.

A graph is defined by its structure, not by how it is drawn or what its vertices are called.

This matters for engineers because the same structural problem can appear in completely different-looking contexts. A dependency graph and a state machine may be isomorphic. Recognizing that lets you reuse the same algorithm.

The graph isomorphism problem — the computational question of deciding whether two given graphs are isomorphic — is one of the few well-known problems whose complexity class is unresolved: it has not been proven to be solvable in polynomial time, yet it has not been proven NP-complete either.

Analogy Bridge

If the formalism above feels abstract, consider an org chart.

• Each person in the org is a vertex.
• Each reporting relationship is an edge.
• Because reporting is directional (Alice reports to Bob, not the other way around), this is a directed graph.
• If you add salaries to each person, that would be a vertex-weighted graph. If you add the number of interactions per week to each relationship, that would be an edge-weighted (weighted) graph.
• A person's in-degree is how many people report to them. Their out-degree is how many people they report to (usually 1, sometimes 0 for the CEO).
• Two people who have a direct reporting relationship are adjacent.

Now swap "person" for "microservice," "reporting relationship" for "API call," and you have a service dependency graph. Same structure, different domain. That is the power — and the point — of graph theory.

Worked Example

Setup. You are given the following graph:

• Vertices: {1, 2, 3, 4}
• Directed edges (arcs): {(1,2), (1,3), (2,4), (3,4), (4,1)}

Answer the following questions.

Question 1. Is this graph directed or undirected?

Directed. The edges are ordered pairs — (1,2) and (2,1) would be distinct arcs. Only (1,2) exists here, not (2,1).

Question 2. What are the in-degree and out-degree of vertex 4?

Count arcs arriving at 4: (2,4) and (3,4) — in-degree = 2. Count arcs leaving 4: (4,1) — out-degree = 1.

Question 3. Which vertices are adjacent to vertex 1?

Vertex 1 has outgoing arcs to 2 and 3, and an incoming arc from 4. In a directed graph, adjacency typically refers to both. Vertices 2, 3, and 4 are all adjacent to vertex 1.

Question 4. Is this a simple graph?

Yes. No pair of vertices has more than one arc between them, and no vertex has a self-loop.

Question 5. Is this graph complete?

No. K_4 would require 4 × 3 / 2 = 6 edges. This graph has 5. Also, vertex 2 and vertex 3 are not connected directly.

Question 6. What would K_4 look like? How many edges?

K_4 has every pair connected: {1,2}, {1,3}, {1,4}, {2,3}, {2,4}, {3,4} — 6 edges, each vertex with degree 3.

Common Misconceptions

"A directed graph is just an undirected graph with arrows on the picture."

This one is subtle but important. Directed and undirected graphs are formally different objects. In an undirected graph, an edge is an unordered pair {A, B}. In a directed graph, an arc is an ordered pair (A, B). The arc (A, B) does not imply the existence of (B, A). When you implement a directed graph, treating it as undirected will silently corrupt your traversal logic.

"The same graph drawn differently is a different graph."

No. A graph is defined by its vertex set and edge set — not by any particular layout. Two drawings that have the same vertices, the same edges, and the same adjacency relationships represent the same graph. This is precisely what graph isomorphism captures: structural identity independent of representation.

"Weights belong on vertices."

Weights most naturally live on edges, because they describe the relationship between two vertices — the cost of going from A to B, the bandwidth between two servers. Vertex weights exist in some formulations, but when someone says "weighted graph" without qualification, they mean edge weights.

"A multigraph is just a weird edge case."

Multigraphs appear in practical engineering contexts more often than the name suggests. A network topology where two routers are connected by multiple physical links is a multigraph. A transport model where two cities are served by both rail and road is a multigraph. The distinction matters when you implement graph storage: an adjacency list for a simple graph and one for a multigraph handle duplicate entries differently.

Quiz

1. A graph G has vertices {A, B, C, D} and edges {AB, BC, CD, DA}. What is the degree of vertex B in this undirected graph?

Show answer

Vertex B is connected to A (edge AB) and C (edge BC). Degree = 2.

---

2. In a directed graph, vertex X has the following arcs: (X, Y), (X, Z), (W, X), (V, X), (X, V). What is the in-degree and out-degree of X?

Show answer

Arcs arriving at X: (W, X) and (V, X) → in-degree = 2. Arcs leaving X: (X, Y), (X, Z), (X, V) → out-degree = 3.

---

3. How many edges does K_6 (the complete graph on 6 vertices) have?

Show answer

n(n−1)/2 = 6 × 5 / 2 = 15 edges.

---

4. You have two graphs:

• G1: vertices {1, 2, 3}, edges {12, 23, 13}
• G2: vertices {P, Q, R}, edges {PQ, QR, PR}

Are G1 and G2 isomorphic? Why or why not?

Show answer

Yes. Both are complete graphs on 3 vertices (K_3). The mapping 1→P, 2→Q, 3→R preserves all adjacency relationships. They are structurally identical — only the labels differ.

---

5. You are modeling an airport network. Between two cities, there are three different airlines operating flights. Should you model this as a simple graph or a multigraph?

Show answer

A multigraph, because multiple distinct edges (one per airline route) connect the same pair of vertices. A simple graph allows at most one edge between any two vertices.