Vertex (Graph Theory)
In 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, the "nouns" of graph theory while edges are the "verbs." Formally, a vertex $v$ in graph $G = (V, E)$ is an element of the vertex set $V$; the degree $\deg(v)$ is the number of edges incident to $v$ (in directed graphs, in-degree and out-degree count separately), and the Handshaking Lemma states the sum of all degrees equals $2|E|$. In spectral graph theory, the adjacency matrix $A$ has $A_{ij} = 1$ if $\{i,j\}$ is an edge; its eigenvalues (the spectrum of $G$) encode structural properties, and the second-smallest eigenvalue of the Laplacian $L = D - A$ is the algebraic connectivity, measuring how well-connected the graph is.
Example
In a map graph, each city is a vertex; in a social network, each person is a vertex. 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$, summing to $8 = 2 \times 4$ edges. For the complete graph $K_n$, every vertex has degree $n-1$, and its adjacency matrix has eigenvalues $n-1$ (once) and $-1$ ($n-1$ times), giving algebraic connectivity $n$, reflecting maximal connectivity.
Key Insight
Vertices are the things being studied, and the Handshaking Lemma implies the number of odd-degree vertices is always even, a parity constraint used in many proofs. Fiedler's eigenvector (corresponding to the second-smallest Laplacian eigenvalue) provides an optimal graph partitioning, used in spectral clustering and graph drawing algorithms.