Vertex (graph theory)
In graph theory, a vertex (plural: vertices) is a fundamental unit representing a node, point, or entity in a graph, connected to other vertices via edges. The degree of a vertex is the number of edges incident to it, and a vertex with degree zero is called an isolated vertex. Vertices model real-world objects such as cities in a road network, computers in a network, or people in a social graph.
Key Formula
degree(v) = number of edges incident to vertex v
LaTeX: \deg(v) = |\{e \in E : v \in e\}|
| Symbol | Meaning | Unit |
|---|---|---|
| deg(v) | Degree of vertex v — the count of edges touching v | none |
| E | Set of all edges in the graph | none |
| e | An individual edge in the graph | none |
Worked Example
Problem
A graph has vertices A, B, C, D with edges AB, AC, BC, CD. Find the degree of each vertex and verify the Handshaking Lemma.
Solution
Step 1: List edges: AB, AC, BC, CD. Step 2: Count edges at each vertex: deg(A) = 2 (edges AB, AC) deg(B) = 2 (edges AB, BC) deg(C) = 3 (edges AC, BC, CD) deg(D) = 1 (edge CD) Step 3: Sum of degrees = 2 + 2 + 3 + 1 = 8. Step 4: Number of edges |E| = 4. By Handshaking Lemma, sum of degrees = 2|E| = 2 × 4 = 8. ✓
Answer
deg(A)=2, deg(B)=2, deg(C)=3, deg(D)=1. Sum = 8 = 2 × 4 edges (Handshaking Lemma verified).
Vertex Degree Classifications
| Degree | Name | Description | Example |
|---|---|---|---|
| 0 | Isolated vertex | No edges attached | Disconnected node in network |
| 1 | Pendant / Leaf | Exactly one edge | Dead-end road |
| 2 | Path vertex | Two edges; interior of a path | Intermediate city on a route |
| k (all same) | k-regular vertex | All vertices have degree k | Vertices in a cycle graph |
| n-1 | Universal vertex | Connected to all other vertices | Hub in a star graph |
Interactive Tools
Wikimedia Commons, CC BY-SA
Related Terms
Edge (graph theory)
In graph theory, an edge is a connection between two vertices (nodes) representing a relationship or link between them. Edges may be directed (pointing from one vertex to another, called arcs) or undirected (bidirectional), and weighted (carrying a numerical value such as distance or cost) or unweighted. The set of all edges in a graph, together with the set of vertices, fully defines the graph's structure.
Graph Theory
Graph theory is the branch of mathematics that studies graphs — mathematical structures consisting of vertices (nodes) connected by edges (links) used to model pairwise relationships between objects. It was founded by Leonhard Euler in 1736 when he solved the Königsberg bridge problem. Graph theory underpins computer networks, social network analysis, circuit design, scheduling algorithms, and shortest-path computations.
Graph Path
A path in a graph is a sequence of vertices in which each consecutive pair is connected by an edge and no vertex is repeated. The length of a path is defined as the number of edges it traverses. Paths are central to graph algorithms such as Dijkstra's shortest-path algorithm, breadth-first search, and depth-first search, which are used in navigation systems, network routing, and AI planning.
The word "vertex" comes from Latin vertex, meaning "highest point" or "whirl," derived from vertere, "to turn." In geometry it referred to the apex of an angle or polygon; its adoption into graph theory follows naturally as the fundamental point from which edges radiate.