Edge (Graph Theory)
Calculus & Advanced MathIn 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. It represents a relationship between those two things.
Example
In a flight map, each flight route is an edge connecting two airport vertices. In a friendship network, each friendship is an edge.
Key Insight
Edges can have extra information: a weighted edge might represent distance or cost; a directed edge (arrow) represents a one-way relationship.
Definition
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. A simple graph has no self-loops or multiple edges between the same pair of vertices.
Example
Dijkstra's shortest path algorithm finds the path from source to target with minimum total edge weight. It requires non-negative edge weights.
Key Insight
Edge density $|E|/|V|^2$ ranges from $0$ (no edges, empty graph) to $1$ (every pair connected, complete graph). Real-world networks like the internet and social networks are sparse (low density) but with interesting local structure.
Definition
In the 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$. By Menger's theorem, $\lambda(G)$ equals the maximum number of edge-disjoint paths between any two vertices.
Example
The edge chromatic number (chromatic index) $\chi'(G)$ is the minimum number of colors to color edges so no two incident edges share a color. Vizing's theorem: $\chi'(G)$ is either $\Delta(G)$ or $\Delta(G)+1$ (where $\Delta$ is maximum degree).
Key Insight
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.