OneNoughtOne
0/364
Loading content...
Read aloud is unavailable in this browser.
If data structures had a periodic table, graphs would be the fundamental elements from which everything else is composed. Arrays, linked lists, trees, and even complex networks all reduce, at their core, to two beautifully simple concepts: vertices (also called nodes) and edges (also called arcs or links).
Understanding vertices and edges isn't merely academic vocabulary—it's the lens through which you'll see social networks, road systems, computer networks, dependency graphs, molecular structures, and countless other real-world systems. This page will give you deep, unshakeable intuition for these foundational concepts.
By the end of this page, you will understand vertices and edges with enough depth to recognize them in any context—whether you're modeling a subway system, analyzing a social network, or optimizing a recommendation engine. You'll know not just what they are, but why they're defined this way and how they encode arbitrary relationships.
A vertex (plural: vertices) is the fundamental unit of a graph. It represents a discrete entity—something that can be identified, labeled, and distinguished from other entities. In mathematical notation, vertices are often denoted by symbols like v, u, w, or by numbers 1, 2, 3, ... or letters A, B, C, ....
The abstraction power of vertices:
What makes vertices extraordinarily powerful is their generality. A vertex can represent:
When modeling real-world problems as graphs, ask yourself: "What are the things I care about?" Each distinct thing becomes a vertex. The rest—how they relate—becomes edges.
Vertex Properties and Attributes:
While a vertex in its purest mathematical form is just an identity—a point without dimension—in practical applications, vertices often carry attributes or properties. These might include:
These attributes don't change the fundamental nature of the vertex—they enrich it for specific applications.
| Domain | What a Vertex Represents | Example Attributes |
|---|---|---|
| Social Network | A person or account | Name, profile picture, follower count |
| Road Network | An intersection or city | GPS coordinates, name, traffic signal status |
| Web Graph | A webpage | URL, page rank, last crawled date |
| Dependency Graph | A module or package | Version, dependencies count, file size |
| Game State | A board configuration | Move count, evaluation score, hash value |
| Circuit Design | A component or gate | Type (AND, OR, NOT), input count, delay |
An edge is a connection between two vertices. Edges encode relationships—the very essence of what makes graphs useful. Without edges, we'd just have a collection of isolated points. With edges, we have structure, meaning, and the ability to ask profound questions about connectivity, paths, and flows.
In mathematical notation, an edge is typically written as an ordered pair (u, v) or unordered pair {u, v} depending on whether the graph is directed or undirected. The vertices u and v are called the endpoints of the edge.
The abstraction power of edges:
Just as vertices abstract "things," edges abstract "relationships between things." An edge can represent:
When modeling problems, ask: "How are my things related?" Each relationship type might become an edge (or a different type of edge in a multi-graph). The semantics of your edges define what "connected" means in your domain.
Edge Properties and Attributes:
Like vertices, edges often carry additional information:
The presence or absence of these attributes shapes what algorithms are applicable and what questions can be answered.
| Domain | What an Edge Represents | Common Attributes |
|---|---|---|
| Social Network | Friendship, follow relationship | Strength, creation date, mutual (boolean) |
| Road Network | Road or highway segment | Distance, speed limit, toll cost |
| Web Graph | Hyperlink from page A to page B | Anchor text, nofollow status |
| Dependency Graph | "A depends on B" relationship | Version constraint, optional (boolean) |
| Flow Network | Pipe or channel | Capacity, current flow |
| Neural Network | Connection between neurons | Weight (learned parameter) |
Graphs are inherently visual structures. The standard visual representation draws vertices as circles (or dots) and edges as lines (or arcs) connecting them. This simple representation has been used since the earliest days of graph theory, dating back to Leonhard Euler's solution to the Seven Bridges of Königsberg in 1736.
A simple example:
Consider a graph with four vertices representing cities: New York (NY), Los Angeles (LA), Chicago (CHI), and Houston (HOU). Suppose there are flights connecting:
This graph has:
A critical insight: the layout of a graph diagram—where vertices are positioned, how edges curve—is purely aesthetic. Two diagrams showing the same vertices and edges represent the same graph, even if they look different. What matters is the connectivity: which vertices are connected to which.
Why visualization matters:
Despite being mathematically independent of layout, visualization remains crucial for:
Throughout your work with graphs, you'll move fluidly between abstract representations (adjacency lists, matrices) and visual intuition.
When a vertex v is an endpoint of an edge e, we say that v and e are incident to each other. This is the fundamental relationship that ties vertices and edges together.
Formal Definition:
Given an edge e = (u, v), we say:
e is incident to vertex ue is incident to vertex vu and v are incident to edge eIncidence is symmetric: if e is incident to v, then v is incident to e.
Why incidence matters:
The incidence relationship is foundational because:
1234567891011121314
Graph: Vertices: {A, B, C, D} Edges: {e1=(A,B), e2=(B,C), e3=(C,D), e4=(A,C)} Incidence relationships: Vertex A is incident to: e1, e4 Vertex B is incident to: e1, e2 Vertex C is incident to: e2, e3, e4 Vertex D is incident to: e3 Observations: - Vertex C has the highest degree (3) — it's incident to 3 edges - Vertex D has the lowest degree (1) — a "leaf" vertex - Each edge is incident to exactly 2 vertices (no self-loops here)Don't confuse incidence with adjacency: Incidence is between vertices and edges ("this vertex touches this edge"). Adjacency is between two vertices ("these vertices share an edge"). We'll explore adjacency in detail in a later page.
The degree of a vertex v, denoted deg(v), is the number of edges incident to that vertex. This simple metric is surprisingly powerful—it reveals local connectivity and plays a central role in graph theory theorems.
Formal Definition:
For an undirected graph G = (V, E):
$$\deg(v) = |{e \in E : v \text{ is an endpoint of } e}|$$
In plain language: count how many edges touch vertex v.
Special degree values:
| Context | Vertex | Degree Interpretation |
|---|---|---|
| Social Network | Popular User | High degree = many friends/followers |
| Road Network | Major Intersection | High degree = many roads meeting |
| Web Graph | Hub Page | High degree = many incoming/outgoing links |
| Collaboration Graph | Prolific Researcher | High degree = many co-authors |
| Airline Network | Major Airport Hub | High degree = many destinations |
Self-loops (edges from a vertex to itself) are counted twice in degree calculations because both endpoints are the same vertex. So if vertex A has a self-loop, that single edge contributes 2 to deg(A). This convention ensures the Handshaking Lemma remains valid.
One of the most elegant results in graph theory is the Handshaking Lemma, which reveals a fundamental constraint on vertex degrees:
$$\sum_{v \in V} \deg(v) = 2|E|$$
In words: The sum of all vertex degrees equals twice the number of edges.
Why is this true?
Each edge has exactly two endpoints. When we sum degrees across all vertices, each edge gets counted once for each of its endpoints—meaning twice total. Hence, the sum of degrees must be exactly double the edge count.
Immediate Corollary:
In any graph, the number of vertices with odd degree must be even. (Otherwise, the sum couldn't equal an even number.)
Why "Handshaking"?
Imagine edges as handshakes between people. Each handshake involves two hands. If we count the total number of hands shaking, we get twice the number of handshakes.
12345678910111213141516
Graph: Vertices: {A, B, C, D, E} Edges: {(A,B), (A,C), (B,C), (B,D), (C,D), (D,E)} |E| = 6 Degree calculation: deg(A) = 2 (edges to B, C) deg(B) = 3 (edges to A, C, D) deg(C) = 3 (edges to A, B, D) deg(D) = 3 (edges to B, C, E) deg(E) = 1 (edge to D) Sum of degrees: 2 + 3 + 3 + 3 + 1 = 12Twice the edges: 2 × 6 = 12 ✓ Vertices with odd degree: B, C, D, E → 4 vertices (even count ✓)The Handshaking Lemma provides a quick sanity check. If someone claims a graph has 10 edges but vertex degrees sum to 19, you know there's an error—the sum must be even. This is useful when validating graph data or debugging graph construction code.
Not all graphs have the same "density" of edges relative to vertices. This distinction profoundly impacts algorithm selection and performance.
Maximum possible edges:
For a simple undirected graph (no self-loops, no duplicate edges) with n vertices:
$$|E|_{max} = \binom{n}{2} = \frac{n(n-1)}{2}$$
This is the number of ways to choose 2 vertices from n—the complete graph.
Edge density:
The density of a graph is the ratio of actual edges to maximum possible edges:
$$\text{density} = \frac{|E|}{\binom{n}{2}} = \frac{2|E|}{n(n-1)}$$
Density ranges from 0 (no edges) to 1 (complete graph).
Most real-world graphs are sparse. The internet has billions of webpages but each links to relatively few others. Social networks have billions of users but average friend counts in the hundreds. This sparsity is what makes graph algorithms practical at scale—if they were dense, even O(n) edge operations would become O(n²).
Understanding vertices and edges conceptually is essential, but as programmers, we ultimately need to represent them in code. Here's a preview of common approaches (we'll explore these deeply in later modules).
Basic vertex representation:
Vertices are often represented as:
Basic edge representation:
Edges are typically represented as:
1234567891011121314151617181920212223242526272829303132333435363738
# Basic graph representation concepts# (Full implementations covered in later modules) # Vertices as integersvertices = [0, 1, 2, 3, 4] # Edges as tuples (source, target)edges = [ (0, 1), # Edge from vertex 0 to vertex 1 (0, 2), # Edge from vertex 0 to vertex 2 (1, 2), # Edge from vertex 1 to vertex 2 (2, 3), # Edge from vertex 2 to vertex 3 (3, 4), # Edge from vertex 3 to vertex 4] # Vertices with attributes (using dictionaries)vertex_data = { 0: {"name": "New York", "population": 8_336_817}, 1: {"name": "Los Angeles", "population": 3_979_576}, 2: {"name": "Chicago", "population": 2_693_976}, 3: {"name": "Houston", "population": 2_320_268}, 4: {"name": "Phoenix", "population": 1_680_992},} # Edges with weights (using tuples with 3 elements)weighted_edges = [ (0, 1, 2462), # NY to LA: 2462 miles (0, 2, 713), # NY to Chicago: 713 miles (1, 3, 1547), # LA to Houston: 1547 miles] # Count vertices and edgesprint(f"Number of vertices: {len(vertices)}") # 5print(f"Number of edges: {len(edges)}") # 5 # Calculate degree for vertex 0degree_0 = sum(1 for u, v in edges if u == 0 or v == 0)print(f"Degree of vertex 0: {degree_0}") # 2We've covered the fundamental building blocks of graph theory. Let's consolidate what we've learned:
What's next:
Now that we understand vertices and edges intuitively, we're ready to formalize graphs mathematically. The next page introduces the formal definition G = (V, E), which provides the precise language used in algorithms and academic literature.
You now understand the atomic components of graphs: vertices represent things, edges represent relationships, and together they can model virtually any network or system. This foundation will support every graph algorithm and concept that follows.