Edge (Graph Theory)
In graph theory, an edge is a connection between two vertices, representing a relationship or link between them.
Definition
An edge in a graph is a line connecting two vertices, representing a relationship between those two things; edges can carry extra information, a weighted edge might represent distance or cost, and a directed edge (arrow) represents a one-way relationship. Formally, an edge $\{u, v\}$ (undirected) or $(u, v)$ (directed) connects vertices $u$ and $v$, a weighted graph assigns a numerical weight $w(e)$ to each edge, and a simple graph has no self-loops or multiple edges between the same pair. In the formal edge-set formalism, $E \subseteq \{\{u,v\}: u,v \in V, u \neq v\}$ for simple undirected graphs; edge connectivity $\lambda(G)$ is the minimum number of edges whose removal disconnects $G$, and by Menger's theorem it equals the maximum number of edge-disjoint paths between any two vertices.
Example
In a flight map, each flight route is an edge connecting two airport vertices; in a friendship network, each friendship is an edge. Dijkstra's shortest path algorithm finds the path from source to target with minimum total edge weight, requiring non-negative weights. The edge chromatic number (chromatic index) $\chi'(G)$ is the minimum number of colors needed so no two incident edges share a color; Vizing's theorem says $\chi'(G)$ is either $\Delta(G)$ or $\Delta(G)+1$, where $\Delta$ is the maximum degree.
Key Insight
Edge density $|E|/|V|^2$ ranges from $0$ (empty graph) to $1$ (complete graph); real-world networks like the internet and social networks are sparse but with interesting local structure. Vizing's theorem partitions graphs into class 1 ($\chi' = \Delta$) and class 2 ($\chi' = \Delta+1$); determining which class a graph belongs to is NP-hard in general, linking edge coloring to computational complexity.