Vertex (Graph Theory)
Calculus & Advanced MathIn graph theory, a vertex is a fundamental node or point in a graph, connected to other vertices by edges.
Definition
In a graph, a vertex (plural: vertices) is one of the dots. Vertices represent objects or locations, and edges between them represent connections.
Example
In a map graph, each city is a vertex. In a social network, each person is a vertex.
Key Insight
Vertices are the "nouns" of graph theory: the things being studied. Edges are the "verbs": the relationships between them.
Definition
A vertex $v$ in graph $G = (V, E)$ is an element of the vertex set $V$. The degree of $v$ ($\deg(v)$) is the number of edges incident to $v$. In directed graphs, in-degree and out-degree count incoming and outgoing edges separately. The Handshaking Lemma: sum of all degrees $= 2|E|$.
Example
In a graph with vertices $\{A,B,C,D\}$ and edges $\{AB,AC,BC,BD\}$: $\deg(A)=2$, $\deg(B)=3$, $\deg(C)=2$, $\deg(D)=1$. Sum $= 8 = 2 \times 4$ edges.
Key Insight
The Handshaking Lemma implies the number of odd-degree vertices is always even, a parity constraint used in many proofs.
Definition
In spectral graph theory, the adjacency matrix $A$ has $A_{ij} = 1$ if $\{i,j\}$ is an edge, $0$ otherwise. The eigenvalues of $A$ (the spectrum of $G$) encode structural properties: the largest eigenvalue relates to graph connectivity; the second smallest eigenvalue of the Laplacian $L = D - A$ (where $D$ is the degree matrix) is the algebraic connectivity, measuring how well-connected the graph is.
Example
For the complete graph $K_n$: every vertex has degree $n-1$. The adjacency matrix has eigenvalues $n-1$ (once) and $-1$ ($n-1$ times). The algebraic connectivity $= n$, reflecting maximal connectivity.
Key Insight
Fiedler's eigenvector (corresponding to the second-smallest Laplacian eigenvalue) provides an optimal graph partitioning, used in spectral clustering and graph drawing algorithms.