Nodes (vertices) and edges connecting them. Directed vs undirected.
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.
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.
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.
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).
Let
Then G = (V, E) describes 4 vertices, with three undirected connections.
You can already ask meaningful questions:
Notice what we did not need:
Different fields prefer different words:
| Common term | Graph theory term | Meaning |
|---|---|---|
| node | vertex | an element of V |
| link/connection | edge | an element of E |
In this node, we’ll use vertex and edge, but remember the synonyms.
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.
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.
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.
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).
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).
| Feature | Undirected graph | Directed graph |
|---|---|---|
| Edge notation | {u, v} | (u, v) |
| Order matters? | no | yes |
| Symmetry implied? | yes: u connected to v implies v connected to u | no: (u, v) does not imply (v, u) |
| Common examples | friendship, roads (two-way) | follows on social media, one-way streets, prerequisites |
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.
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).
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.
The biggest modeling choice you make with graphs is whether relationships are mutual.
This choice changes what questions make sense.
Suppose V = {A, B}.
If you want mutual connection in a directed graph, you must include both edges:
It helps to explicitly name what kind of elements E contains.
Undirected:
Directed:
So the same symbol “edge” hides two different underlying data types.
Even before full algorithms, you can define a path informally:
Undirected example:
Directed example:
This is where direction matters:
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.
2) 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.
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.
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.
| Scenario | Vertices (V) | Edges (E) | Directed? |
|---|---|---|---|
| Social network friendships | people | friendships | usually undirected |
| Social media “follows” | accounts | follow links | directed |
| Road network | intersections/cities | roads | depends (two-way vs one-way) |
| Web graph | web pages | hyperlinks | directed |
| Course prerequisites | courses | “is prerequisite of” | directed |
| Computer network | devices | cables/connections | often undirected; can be directed for routing policies |
To run algorithms, you must store a graph in memory.
Two classic representations are:
Those are the focus of the next node: Graph Representations.
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.
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.
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).
Identify the vertex set:
V = {Ava, Ben, Chen, Dia}
Translate each friendship into an undirected edge (unordered pair):
Ava–Ben becomes {Ava, Ben}
Ava–Dia becomes {Ava, Dia}
Ben–Chen becomes {Ben, Chen}
Collect edges into the edge set:
E = {{Ava, Ben}, {Ava, Dia}, {Ben, Chen}}
Write the graph as a pair:
G = (V, E)
Compute degrees by counting incident edges:
Insight: The graph definition is just careful bookkeeping with sets. The modeling choice “friendship is mutual” forces undirected edges.
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?
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.
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.
For G₂ (directed), edges are ordered:
(A, B) is A → B.
(B, C) is B → C.
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.
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.
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).
List outgoing edges from each requested vertex:
Edges leaving 1 are (1, 2) and (1, 3).
So deg⁺(1) = 2.
List incoming edges to 1:
The only edge entering 1 is (4, 1).
So deg⁻(1) = 1.
Outgoing edges from 2:
Look for edges of the form (2, x). None appear.
So deg⁺(2) = 0.
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.
A graph is defined as G = (V, E) with V a set of vertices and E a set of edges.
Undirected edges are unordered pairs {u, v}, so {u, v} = {v, u}.
Directed edges are ordered pairs (u, v), so (u, v) ≠ (v, u) in general.
Adjacency means “connected by an edge”; in directed graphs you often distinguish out-neighbors vs in-neighbors.
Degree counts incident edges; in directed graphs it splits into out-degree deg⁺(v) and in-degree deg⁻(v).
Most early graph questions (paths, reachability, connectivity) depend critically on whether edges are directed.
Before solving a graph problem, clarify what vertices represent, what edges represent, and whether the graph is directed.
Treating directed edges as if they were undirected (assuming (u, v) implies (v, u)).
Mixing up edge notation: writing {u, v} for a directed edge or (u, v) for an undirected one without stating intent.
Forgetting that in a simple graph you typically exclude self-loops (v, v) and duplicate edges unless explicitly allowed.
Confusing degree in a directed graph: using a single deg(v) without specifying in-degree vs out-degree.
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.
(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.
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.
(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.
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.
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.