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.
Key Formula
Maximum number of edges in a simple undirected graph with n vertices = n(n-1)/2
LaTeX: |E| \leq \frac{n(n-1)}{2}
| Symbol | Meaning | Unit |
|---|---|---|
| |E| | Number of edges in the graph | none |
| n | Number of vertices in the graph | none |
Worked Example
Problem
A complete graph K₅ has 5 vertices. How many edges does it contain? Then verify using the Handshaking Lemma.
Solution
Step 1: Use the formula for a complete graph: |E| = n(n-1)/2 = 5 × 4 / 2 = 10 edges. Step 2: In K₅, every vertex has degree n-1 = 4 (connected to all other 4 vertices). Step 3: Sum of all degrees = 5 vertices × 4 = 20. Step 4: Handshaking Lemma: sum of degrees = 2|E|, so 2|E| = 20, giving |E| = 10. ✓
Answer
K₅ contains 10 edges. Verified by Handshaking Lemma: sum of degrees (20) = 2 × 10.
Types of Edges in Graph Theory
| Edge Type | Symbol | Direction | Weight | Example |
|---|---|---|---|---|
| Undirected edge | {u, v} | Both ways | No | Mutual friendship on Facebook |
| Directed edge (arc) | (u, v) | u → v only | No | Twitter follow (one-way) |
| Weighted undirected | {u, v, w} | Both ways | Yes (w) | Road distance between cities |
| Weighted directed | (u, v, w) | u → v only | Yes (w) | One-way flight with fare |
| Self-loop | (v, v) | Self | Optional | Web page linking to itself |
Interactive Tools
Wikimedia Commons, CC BY-SA
Related Terms
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.
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.
Euler Path
An Euler path (or Eulerian path) is a trail in a graph that visits every edge exactly once, without necessarily returning to the starting vertex. An Euler circuit (or Eulerian circuit) is an Euler path that begins and ends at the same vertex. A connected graph has an Euler path if and only if it has exactly zero or two vertices of odd degree; if two odd-degree vertices exist, the path must start and end at those vertices.
The term "edge" in mathematics comes from the Old English ecg, meaning "corner" or "boundary," related to Old High German ecka. In graph theory, the term was popularised by Sylvester (1878) and König (1936) to describe the line segments connecting vertices in a diagram of a graph.