Graph terminology
A compact glossary for vertices, edges, connectivity, and common graph families. Definitions follow usual discrete-math / algorithms texts; conventions for “simple path” or “degree of loop” may vary slightly.
Tables on this page
- Structure — graph, vertices, edges
- Adjacency and degree
- Walks, paths, cycles
- Directed graphs and weighted edges
1) Structure
| Term | Meaning |
|---|---|
| Graph | A pair G = (V, E): vertices (nodes) V and edges E connecting pairs (or ordered pairs if directed). |
| Vertex (node) | An entity in V; often stores an id or data in implementations. |
| Edge | A connection between two vertices; may be undirected {u,v} or directed (u,v). |
| Adjacent | Two vertices joined by an edge are neighbors (adjacent). |
| Loop | An edge from a vertex to itself (allowed or forbidden depending on “simple graph” definition). |
| Multigraph | Multiple edges between the same pair of vertices may exist. |
2) Adjacency and degree
| Term | Meaning |
|---|---|
| Degree (undirected) | Number of edge ends incident to v (loops sometimes count twice). |
| In-degree / out-degree | For directed graphs: count of edges into vs out of a vertex. |
| Handshaking lemma | Undirected: sum of degrees = 2|E| — useful sanity check. |
| Sparse vs dense | Sparse: |E| much less than |V|²; dense: many possible edges present (adjacency matrix may pay off). |
3) Walks, paths, cycles
| Term | Meaning |
|---|---|
| Walk | Sequence of vertices where consecutive vertices are adjacent; vertices/edges may repeat. |
| Trail | Walk with no repeated edges. |
| Path | Usually a simple path: no repeated vertices (definitions vary slightly). |
| Cycle | Closed walk with distinct vertices except start = end (length ≥ 2 or 3 by convention). |
| Connected | Undirected graph: path between every pair of vertices. Directed: strongly / weakly connected variants. |
| Component | Maximal connected subgraph. |
4) Directed graphs and weights
| Term | Meaning |
|---|---|
| Directed graph (digraph) | Edges are arrows; asymmetry matters for reachability. |
| DAG | Directed acyclic graph — no directed cycles; enables topological sorting. |
| Weighted graph | Each edge has a numeric weight (distance, cost, capacity). |
| Subgraph | Graph formed from a subset of vertices and edges of G. |
Key takeaway
Be explicit about directed vs undirected, whether edges are weighted, and whether “path” means simple — your C loops and complexity analysis depend on it.
Next up: Graph applications · Graph representation · Graph types