What is the difference between a vertex and a node?

In graph theory, 'vertex' and 'node' mean the same thing. 'Vertex' is the standard mathematical term, while 'node' is more common in computer science and networking contexts. Both refer to a point in a graph where edges can meet.

Graph Vertex — Definition, Formula & Examples

A graph vertex is a single point or node in a graph that can be connected to other vertices by edges. Vertices are the fundamental building blocks of any graph structure.

In graph theory, a vertex (plural: vertices) is an element of the set $V$ in a graph $G = (V, E)$ , where $V$ is a finite nonempty set and $E$ is a set of unordered pairs of distinct elements of $V$ called edges. Each vertex serves as an endpoint for zero or more edges.

Key Formula

\sum_{v \in V} \deg(v) = 2|E|

Where:

$v$ = A vertex in the vertex set V
$\deg(v)$ = The degree of vertex v — the number of edges incident to it
$|E|$ = The total number of edges in the graph

How It Works

When you work with graphs, you start by identifying the vertex set — the collection of objects you want to study relationships between. Each vertex represents an entity such as a city, a person, or a computer. Edges then connect pairs of vertices to show a relationship. The number of edges attached to a vertex is called its degree. By analyzing vertex degrees and connections, you can solve problems about networks, scheduling, routing, and social connections.

Worked Example

Problem: A graph G has vertex set V = {A, B, C, D} and edge set E = {(A,B), (A,C), (B,C), (B,D)}. Find the degree of each vertex and verify the Handshaking Lemma.

Step 1: Count the edges attached to each vertex. Vertex A appears in edges (A,B) and (A,C), so its degree is 2.

\deg(A) = 2

Step 2: Vertex B appears in edges (A,B), (B,C), and (B,D), so its degree is 3. Vertex C appears in (A,C) and (B,C), giving degree 2. Vertex D appears only in (B,D), giving degree 1.

\deg(B) = 3, \quad \deg(C) = 2, \quad \deg(D) = 1

Step 3: Sum all degrees and compare with twice the number of edges.

\sum \deg(v) = 2 + 3 + 2 + 1 = 8 = 2 \times 4 = 2|E|

Answer: The degrees are: deg(A) = 2, deg(B) = 3, deg(C) = 2, deg(D) = 1. The sum of degrees equals 8, which is exactly 2 × 4 edges, confirming the Handshaking Lemma.

Another Example

Problem: In a social network with 5 people, every pair of people is friends. How many vertices and edges does the complete graph have, and what is each vertex's degree?

Step 1: Each person is a vertex, so the graph has 5 vertices. This is the complete graph K₅.

|V| = 5

Step 2: In a complete graph, every vertex connects to every other vertex. Each vertex has degree n − 1.

\deg(v) = 5 - 1 = 4

Step 3: Use the Handshaking Lemma to find the total number of edges.

|E| = \frac{\sum \deg(v)}{2} = \frac{5 \times 4}{2} = 10

Answer: The complete graph K₅ has 5 vertices, each with degree 4, and 10 edges in total.

Why It Matters

Vertices form the foundation of discrete mathematics and graph theory, topics covered in courses like AP Computer Science and college-level combinatorics. Network engineers model routers as vertices to optimize internet traffic, and biologists represent species as vertices in food webs. Understanding what a vertex is and how degree works unlocks everything from shortest-path algorithms to social network analysis.

Common Mistakes

Mistake: Confusing the number of vertices with the number of edges when counting connections.

Correction: An edge always connects exactly two vertices. A graph with 5 vertices does not necessarily have 5 edges — the number of edges depends on which pairs are connected.

Mistake: Forgetting that each edge contributes 1 to the degree of both its endpoints, not just one.

Correction: Every edge is shared by two vertices, so the sum of all degrees always equals twice the number of edges (the Handshaking Lemma).