What is a graph, really? — A tool for making relationships visible

From the bridges of Konigsberg to social networks, dependency management, and scheduling, an astonishing variety of problems reduce to graphs. This article explains the intuition behind undirected, directed, and weighted graphs, and why this abstraction is so powerful.

Folio Official

March 1, 2026

Open any graph theory textbook and you will find the declaration " $G = (V, E)$ " on the first page, stated with the calm assurance of self-evident truth. What the textbook rarely explains is why this abstraction is worth adopting. In this article, we will see that the concept of a graph – "a picture of relationships" – provides a unified language for a remarkably wide range of problems.

1 It all began with the bridges of Königsberg

In 1736, the mathematician Euler posed a deceptively simple question about the city of Kö

Euler's brilliant insight was that the shapes of the islands and riverbanks do not matter. All that matters is which landmasses are connected by which bridges– the connectivity relation alone.

By representing landmasses as points (vertices) and bridges as lines (edges), Euler created what we now call a graph.

2 Graphs are everywhere

The power of the graph abstraction lies in the sheer diversity of phenomena that reduce to the same formal structure.

Example 1 (Social networks).

Let each user be a vertex and each friendship be an edge. Facebook's friendship network is then an enormous undirected graph. Clustering phenomena – the tendency for people with many mutual friends to become connected – can be described and analyzed precisely in the language of graph theory.

Example 2 (Package dependencies).

When you install libraries with npm or pip, the dependency relationships form a directed graph. If package

A

depends on package

B

, draw an edge

A \to B

. The absence of circular dependencies is equivalent to saying that this graph is acyclic (i.e., it is a DAG).

Example 3 (Scheduling).

When tasks carry precedence constraints – "

A

must be completed before

B

" – the problem becomes one of topological sorting in a directed graph.

graph TD
    subgraph "Social network (undirected)"
        U1["Alice"] --- U2["Bob"]
        U2 --- U3["Carol"]
        U1 --- U3
    end
    subgraph "Dependencies (directed)"
        P1["React"] --> P2["react-dom"]
        P1 --> P3["scheduler"]
        P2 --> P3
    end

    style U1 fill:#f5f5f5,stroke:#333,color:#000
    style U2 fill:#f5f5f5,stroke:#333,color:#000
    style U3 fill:#f5f5f5,stroke:#333,color:#000
    style P1 fill:#f5f5f5,stroke:#333,color:#000
    style P2 fill:#f5f5f5,stroke:#333,color:#000
    style P3 fill:#f5f5f5,stroke:#333,color:#000

3 The formal definition – turning intuition into mathematics

To treat all of these examples within a single framework, we need precise definitions.

Definition 4 (Undirected graph).

An undirected graph

G = (V, E)

consists of a set

V

of vertices and a family

E \subseteq (2 V)

of two-element subsets of

V

. Each

{u, v} \in E

is called an edge of

G

Definition 5 (Directed graph).

A directed graph

G = (V, A)

consists of a set

V

of vertices and a set

A \subseteq V \times V

of ordered pairs. Each

(u, v) \in A

is called an arc.

There is an important subtlety here. An edge ${u, v}$ in an undirected graph is a set, so ${u, v} = {v, u}$ ; but an arc $(u, v)$ in a directed graph is an ordered pair, so $(u, v) \neq = (v, u)$ in general. Friendship is symmetric (undirected); dependency is not (directed). The mathematics captures this distinction exactly.

Definition 6 (Weighted graph).

A graph equipped with a function

w : E \to R

that assigns a real-valued weight to each edge (or arc) is called a weighted graph.

Example 7.

In a road network model, vertices represent intersections, edges represent roads, and weights represent distances or travel times. The shortest-route computation performed by a GPS navigator is, quite literally, a shortest-path problem on a weighted graph.

4 Why this abstraction is so powerful

Remark 8.

The strength of graphs lies in what they discard. When analyzing a social network, we forget (at least temporarily) the users' ages, hobbies, and locations, and retain only the connectivity pattern: who is connected to whom. Once we do this, problems from entirely different domains become solvable by the same algorithm. Running BFS to find "friends of friends" in a social network and running BFS to trace package dependencies are, from the computer's perspective, the same operation.

5 Basic vocabulary – a shared language

Before proceeding further in graph theory, let us collect the essential terminology.

Definition 9 (Degree).

In an undirected graph, the number of edges incident to a vertex

v

is called the degree of

v

, written

de g (v)

Theorem 10 (Handshaking lemma).

For any undirected graph

G = (V, E)

v \in V \sum de g (v) = 2∣ E ∣.

This follows from the simple observation that each edge contributes exactly one to the degree of each of its two endpoints. Simple as it is, the handshaking lemma is surprisingly powerful: it implies immediately, for instance, that the number of vertices of odd degree is always even.

Definition 11 (Walks, trails, paths, and cycles).

A sequence of vertices

v_{0}, v_{1}, \dots, v_{k}

with

{v_{i}, v_{i + 1}} \in E

for each

i

is called a walk. If no edge is repeated, the walk is a trail; if no vertex is repeated, it is a path. A walk with

v_{0} = v_{k}

and no repeated vertices (other than the endpoints) is called a cycle. A graph is connected if there exists a path between every pair of vertices.

6 Takeaway – graphs as an operating system for thought

A graph is not merely a picture of dots and lines. It is a universal language for reasoning about relationships. The fact that the bridges of Kö

In the next article, we turn to the question of how to walk through a graph. Why does BFS find shortest paths? The answer is a beautiful analogy with ripples on a pond.

Graph Theory Mathematics Between the Lines

Folio Official

Mathematics "between the lines" — exploring the intuition textbooks leave out, written in LaTeX on Folio.

1 フォロワー·105 記事

What is a graph, really? — A tool for making relationships visible

1 It all began with the bridges of Königsberg

2 Graphs are everywhere

3 The formal definition – turning intuition into mathematics

4 Why this abstraction is so powerful

5 Basic vocabulary – a shared language

6 Takeaway – graphs as an operating system for thought

あなたの専門知識を世界に発信しよう

Folio Officialの他の記事

Monetizing Your Articles — How to Earn Revenue Safely with Stripe Connect

Mastering Theorem Environments — theorem, definition, proof, and Friends

Combinatorial Designs and Latin Squares: Balanced Arrangements

Burnside's Lemma and P\'olya Enumeration: Counting Under Symmetry