Graphs Introduction

←Back to Tech Tree

inventorycoverage

Graphs Introduction #

Graph TheoryDifficulty: ★☆☆☆☆Depth: 1Unlocks: 18

Nodes (vertices) and edges connecting them. Directed vs undirected.

Interactive Visualization #

⏮◀◀▶▶STEP0.25x1xZOOM

t=0s

Core Concepts #

Key Symbols & Notation #

G = (V, E): graph specified by vertex set V and edge set E

Essential Relationships #

Prerequisites (1) #

Sets6 atoms

Unlocks (2) #

Graph Representationslvl 2Treeslvl 2

Referenced by (1) #

Where this concept shows up in the operating-finance and personal-finance graphs.

From Business (1) #

[Chart of AccountsBusiness

The concept explicitly frames the chart of accounts as a directed graph - parent accounts point to children, value flows along edges - making graph theory the precise mathematical foundation for the 'walk the edges' analysis it prescribes](/business/chart-of-accounts/)

Advanced Learning Details

Graph Position #

11

Depth Cost

18

Fan-Out (ROI)

10

Bottleneck Score

1

Chain Length

Cognitive Load #

5

Atomic Elements

26

Total Elements

L0

Percentile Level

L3

Atomic Level

All Concepts (10) #

Teaching Strategy #

Self-serve tutorial - low prerequisites, straightforward concepts.

When you model “things and relationships”—friends in a social network, pages linked on the web, cities connected by roads—you’re already thinking in graphs. Graphs give a simple language for turning real-world connections into something you can reason about and compute on.

TL;DR:

A graph is a pair G = (V, E) where V is a set of vertices (nodes) and E is a set of edges (connections). In an undirected graph, edges are unordered pairs {u, v}. In a directed graph, edges are ordered pairs (u, v) that point from u to v. This lesson builds the basic vocabulary so you can describe and analyze network-like structures precisely.

What Is a Graph? #

Why graphs matter #

Many problems aren’t about a single object—they’re about relationships between objects.

Graphs are the mathematical tool for expressing these situations with minimal assumptions.

Formal definition #

A graph is written as:

G = (V, E)

Since you already know sets, you can think of a graph as “two sets packaged together”: a set of things (V) and a set of connections (E).

A first concrete example #

Let

Then G = (V, E) describes 4 vertices, with three undirected connections.

You can already ask meaningful questions:

Notice what we did not need:

Terminology: “node” vs “vertex”, “edge” vs “link” #

Different fields prefer different words:

Common termGraph theory termMeaning
nodevertexan element of V
link/connectionedgean element of E

In this node, we’ll use vertex and edge, but remember the synonyms.

What graphs do not automatically include #

A basic graph definition doesn’t automatically assume:

Those are all extensions. Here, we’ll focus on the most standard intro: simple directed and undirected graphs.

Vertices and Edges (The Building Blocks) #

Vertices: the “things” #

A vertex is a single entity. Formally, it’s just an element v ∈ V.

Because V is a set, vertices are distinct objects. That means you don’t have two different vertices that are both literally “A” inside the same set.

Example:

The symbols don’t matter; the structure comes from edges.

Edges: the “relationships” #

An edge says that two vertices are connected in some way.

But “connected” depends on the graph type:

We’ll unpack that carefully, because it’s the core distinction in this lesson.

Undirected edges as unordered pairs #

In an undirected graph, an edge between u and v is written:

Because sets are unordered:

So the edge does not “point” anywhere. It just says “u and v are connected.”

If G is an undirected graph:

That expression reads: E is a subset of all possible two-vertex sets from V (excluding self-loops for a simple graph).

Directed edges as ordered pairs #

In a directed graph (often called a digraph), an edge is written:

Now order matters:

Interpretation: the edge goes from u to v.

Formally, if G is directed, we typically have:

where V × V is the Cartesian product (all ordered pairs).

A quick comparison table #

FeatureUndirected graphDirected graph
Edge notation{u, v}(u, v)
Order matters?noyes
Symmetry implied?yes: u connected to v implies v connected to uno: (u, v) does not imply (v, u)
Common examplesfriendship, roads (two-way)follows on social media, one-way streets, prerequisites

Neighbors and adjacency (informal but essential) #

Two vertices are adjacent (or neighbors) if they share an edge.

This simple idea—who is adjacent to whom—will later become the basis for graph representations like adjacency lists and adjacency matrices.

Degree: how many edges touch a vertex #

Graphs invite “local counting” questions.

Undirected degree

The degree of a vertex v, written deg(v), is the number of edges incident to v (edges that touch v).

Example: If E = {{A, B}, {A, C}, {A, D}}, then deg(A) = 3.

Directed degree

In directed graphs, edges have direction, so we split degree into:

Example: If E = {(A, B), (A, C), (D, A)}, then:

Degree is not just vocabulary: it’s often a first signal of “important” nodes (high degree) or bottlenecks (nodes with special in/out patterns).

A small but important boundary: self-loops and multi-edges #

In many introductory settings, we assume a simple graph:

But in real systems you might allow them:

Those lead to multigraphs. For this node, keep the simple case in mind unless stated otherwise.

Directed vs Undirected: The Core Mechanic #

Why this distinction is fundamental #

The biggest modeling choice you make with graphs is whether relationships are mutual.

This choice changes what questions make sense.

Same vertices, two different meanings #

Suppose V = {A, B}.

If you want mutual connection in a directed graph, you must include both edges:

Thinking in sets: what exactly is E? #

It helps to explicitly name what kind of elements E contains.

Undirected:

Directed:

So the same symbol “edge” hides two different underlying data types.

Paths (a gentle preview) #

Even before full algorithms, you can define a path informally:

Undirected example:

Directed example:

This is where direction matters:

Converting between directed and undirected models #

Sometimes you’re given one type but want the other.

  1. Forget direction (make an undirected version)

Given a directed graph G = (V, E), define an undirected edge {u, v} whenever at least one of (u, v) or (v, u) is in E.

This is useful when direction is noise or when you care only about whether there is any connection.

  1. Add direction (make a directed version)

Given an undirected graph, you can replace each {u, v} with two directed edges (u, v) and (v, u).

This is useful when your algorithms are written for digraphs but the relationship is mutual.

A note on notation with vectors #

In this lesson, you might see vectors like v in later graph topics (e.g., representing vertices as indices, or adjacency vectors). Here, vertices are usually symbols like u, v, w (scalars in notation), not vectors. We’ll reserve v for actual vectors in later nodes.

Applications and Connections (How Graphs Show Up in CS) #

Why computer science loves graphs #

Graphs are a universal “data structure for relationships.” Once you can describe something as G = (V, E), many standard tools become available:

This node is about vocabulary, but it’s worth seeing where it leads.

Common modeling patterns #

ScenarioVertices (V)Edges (E)Directed?
Social network friendshipspeoplefriendshipsusually undirected
Social media “follows”accountsfollow linksdirected
Road networkintersections/citiesroadsdepends (two-way vs one-way)
Web graphweb pageshyperlinksdirected
Course prerequisitescourses“is prerequisite of”directed
Computer networkdevicescables/connectionsoften undirected; can be directed for routing policies

How this enables representations #

To run algorithms, you must store a graph in memory.

Two classic representations are:

Those are the focus of the next node: Graph Representations.

How this connects to trees #

A tree is a special kind of graph (informally: connected and without cycles). If you understand vertices and edges, you can define trees precisely and see why they’re useful for hierarchy and recursion.

That’s the next major structure unlocked by this node: Trees.

Mental checklist when someone says “graph” #

Before you do anything else, ask:

  1. What are the vertices, exactly?

  2. What does an edge mean in the real world?

  3. Is the relationship directed or undirected?

  4. Are self-loops or multiple edges allowed?

  5. Do edges have weights or labels? (not in this node, but often later)

Getting these answers early prevents confusion later.

Worked Examples (3) #

Build G = (V, E) from a story (Undirected) #

Four people {Ava, Ben, Chen, Dia}. Friendships: Ava is friends with Ben and Dia. Ben is friends with Chen. (Friendship is mutual.) Write the graph G = (V, E) and compute deg(Ava), deg(Ben).

  1. Identify the vertex set:

    V = {Ava, Ben, Chen, Dia}

  2. Translate each friendship into an undirected edge (unordered pair):

    Ava–Ben becomes {Ava, Ben}

    Ava–Dia becomes {Ava, Dia}

    Ben–Chen becomes {Ben, Chen}

  3. Collect edges into the edge set:

    E = {{Ava, Ben}, {Ava, Dia}, {Ben, Chen}}

  4. Write the graph as a pair:

    G = (V, E)

  5. Compute degrees by counting incident edges:

    • •deg(Ava) = 2 because {Ava, Ben} and {Ava, Dia} touch Ava
    • •deg(Ben) = 2 because {Ava, Ben} and {Ben, Chen} touch Ben

Insight: The graph definition is just careful bookkeeping with sets. The modeling choice “friendship is mutual” forces undirected edges.

Directed vs undirected edges change reachability #

Let V = {A, B, C}. Consider two graphs on the same vertices:

G₁ (undirected): E₁ = {{A, B}, {B, C}}

G₂ (directed): E₂ = {(A, B), (B, C)}

In each graph, is there a path from C to A?

  1. For G₁ (undirected), edges are unordered:

    {A, B} means A—B and B—A are effectively the same connection.

    {B, C} means B—C and C—B are also connected.

  2. Check C to A in G₁:

    C—B is allowed because {B, C} ∈ E₁.

    B—A is allowed because {A, B} ∈ E₁.

    So a path exists: C–B–A.

  3. For G₂ (directed), edges are ordered:

    (A, B) is A → B.

    (B, C) is B → C.

  4. Check C to A in G₂:

    From C, there are no outgoing edges listed (no edge of the form (C, ·)).

    So you cannot start a directed path leaving C.

    Therefore, no directed path exists from C to A.

  5. Optionally, note the reverse direction:

    In G₂ there is a directed path from A to C: A → B → C.

Insight: Direction turns “connectedness” into a one-way notion. In directed graphs, you must follow arrow orientation; in undirected graphs, every edge is traversable both ways.

Compute in-degree and out-degree in a digraph #

Let V = {1, 2, 3, 4} and E = {(1, 2), (1, 3), (3, 2), (4, 1)}. Compute deg⁺(1), deg⁻(1), deg⁺(2), deg⁻(2).

  1. List outgoing edges from each requested vertex:

    Edges leaving 1 are (1, 2) and (1, 3).

    So deg⁺(1) = 2.

  2. List incoming edges to 1:

    The only edge entering 1 is (4, 1).

    So deg⁻(1) = 1.

  3. Outgoing edges from 2:

    Look for edges of the form (2, x). None appear.

    So deg⁺(2) = 0.

  4. Incoming edges to 2:

    Edges entering 2 are (1, 2) and (3, 2).

    So deg⁻(2) = 2.

Insight: In directed graphs, “how connected” splits into two different questions: how many edges leave vs how many arrive. Many algorithms (like ranking or flow) depend on this split.

Key Takeaways #

Common Mistakes #

Practice #

easy

Let V = {a, b, c, d} and E = {{a, b}, {b, c}, {c, d}} (undirected). (1) Write G = (V, E). (2) Compute deg(b) and deg(d). (3) Is there a path from a to d?

Hint: Degree counts edges touching the vertex. A path can hop along consecutive edges.

Show solution

(1) G = (V, E) with V = {a, b, c, d} and E = {{a, b}, {b, c}, {c, d}}.

(2) deg(b) = 2 because {a, b} and {b, c} touch b. deg(d) = 1 because only {c, d} touches d.

(3) Yes: a–b–c–d is a path since each consecutive pair is an edge.

medium

Let V = {A, B, C}. Consider the directed graph with E = {(A, B), (B, A), (B, C)}. (1) Compute deg⁺(B) and deg⁻(B). (2) Is there a directed path from C to A?

Hint: Out-degree: edges starting at B. In-degree: edges ending at B. For a path from C, you need an edge leaving C.

Show solution

(1) Edges leaving B: (B, A), (B, C), so deg⁺(B) = 2. Edges entering B: (A, B), so deg⁻(B) = 1.

(2) No. There are no edges of the form (C, x), so C has out-degree 0 and cannot start a directed path to A.

easy

You are modeling airline flights between cities. For each pair of cities u and v, there may be a flight u → v without necessarily having v → u. Should your graph be directed or undirected? Write a one-sentence justification, then describe what V and E represent.

Hint: Ask whether the relationship is inherently one-way or two-way.

Show solution

Directed. A flight from u to v does not imply a flight from v to u.

V is the set of cities, and E is the set of directed edges (u, v) representing an available flight from city u to city v.

Connections #

Quality: A (4.6/5)

← back to treebrowse all →