---
title: 'The Concept of a Graph'
source: 'https://academia.sh/en/courses/data-structures/concept-of-a-graph'
course: 'Data Structures'
language: en
updated: '2026-08-17T18:07:52+00:00'
license: 'CC BY-SA 4.0'
---

# The Concept of a Graph

Vertex and edge definitions, directed and undirected graphs, weight, degree, path, and cycle concepts.

Trees carried two constraints: no cycles, and every node had exactly one parent. Removing
those constraints produces the most general structure for modeling relationships.

A **graph** consists of vertices and the edges that connect them. Such a simple
definition having such a wide range of applications comes from the relationship itself
being a fundamental concept: connections between roads, acquaintance between people,
dependency between tasks, links between pages — all of these are the same structure.

## Basic Terms

A graph is written as $G = (V, E)$: $V$ is the set of vertices, $E$ is the set of edges.

| Term | Meaning |
|---|---|
| Vertex | The unit of the structure; the entity being modeled |
| Edge | A relationship between two vertices |
| Neighbor | Vertices connected by an edge |
| Degree | The number of edges attached to a vertex |
| Path | A sequence of vertices following edges |
| Cycle | A path that returns to the vertex it started from |
| Connected component | A set of vertices that can reach one another within itself |

If one vertex can **reach** another, a path exists between them. A graph in which every
pair of vertices can reach each other is called **connected**; if some pairs cannot, the
graph is split into multiple **components**.

## Directed and Undirected

In an **undirected graph** an edge is two-way: if an edge exists between `a` and `b`, one
can go from `a` to `b` and from `b` to `a`. It models mutual relationships — a road
between two cities, a friendship between two people.

In a **directed graph** an edge has a direction. It models one-way relationships — a link
from one page to another, one task's dependency on another, a one-way street.

In a directed graph, degree splits into two: **in-degree** (the number of edges arriving
at a vertex) and **out-degree** (the number leaving it). This distinction becomes
decisive in the topological sort lesson.

The concept of a cycle also specializes in directed graphs. A **directed acyclic graph**
is a graph that contains no directed cycle, and it is the natural model of dependency
relationships: a task cannot depend on itself, even indirectly.

## Weight

A numeric value — a **weight** — can be assigned to edges. Weight carries the cost or
strength of the relationship: the distance between two cities, the latency of a
connection, the duration of an operation.

In an unweighted graph, the "shortest path" is the one using the fewest edges. In a
weighted graph it is the path with the smallest sum of weights, and the two paths can
differ: whether a few long edges or many short edges is cheaper can only be answered by
looking at the weights.

## Trees Are a Special Case of Graphs

The definition from the previous topic fits into place here: **a tree is an acyclic,
connected, undirected graph.** That a tree with $n$ vertices has $n-1$ edges was a
direct consequence of that definition.

The relationship is built in three steps:

- Removing cycles from a graph produces a **forest**.
- A forest that is connected becomes a **tree**.
- Choosing a vertex of a tree as the root produces a **rooted tree**.

This means every structure from the previous topic is a special case of a graph. The
reverse does not hold: graphs model what trees cannot — cycles, multiple paths, more
than one parent.

The "connected component" question from the disjoint-sets lesson connects here as well:
which vertices belong to the same component as edges are added was tracked there with
union–find.

## Special Graph Families

| Family | Definition | Example use |
|---|---|---|
| Directed acyclic graph | Directed, no cycles | Task dependencies, build order |
| Bipartite graph | Vertices split into two groups, edges only between groups | Matching problems |
| Complete graph | An edge between every pair of vertices | Worst-case analysis |
| Sparse / dense graph | Edge count close to vertex count / close to its square | Determines the representation choice |

The last row is the subject of the next lesson: the ratio of edge count to vertex count
directly determines which representation is suitable.

Bounds on edge count also follow from this distinction. In a simple, undirected graph
the maximum number of edges is:

$$
\lvert E \rvert \leq \frac{\lvert V \rvert (\lvert V \rvert - 1)}{2}
$$

So edge count is bounded by the square of vertex count. Most real graphs stay far below
this bound — in a road network, each city connects to only a handful of neighbors. This
observation explains why representation choice in practice is made with sparse graphs in
mind.

## A Modeling Example

Let the connections between measurement stations be modeled as a graph: stations are
vertices, the communication lines between them are edges, and a line's latency is its
weight.

```python
# Undirected, weighted graph: each edge is written once.
edges = [
    ("north",  "center", 4),
    ("south",  "center", 2),
    ("east",   "center", 7),
    ("west",   "north",  3),
    ("west",   "south",  5),
]

vertices = {v for edge in edges for v in edge[:2]}
print(sorted(vertices))        # ['center', 'east', 'north', 'south', 'west']
print(len(vertices), len(edges))     # 5 5

degree: dict[str, int] = {v: 0 for v in vertices}
for a, b, _ in edges:
    degree[a] += 1
    degree[b] += 1

print(sorted(degree.items()))
# [('center', 3), ('east', 1), ('north', 2), ('south', 2), ('west', 2)]
print(sum(degree.values()), 2 * len(edges))    # 10 10
```

The last line shows the most basic identity of graph theory: **the sum of degrees is
twice the number of edges.** Because each edge contributes one to each of two vertices'
degrees, this holds in every undirected graph. A direct consequence is that the number
of odd-degree vertices is always even.

Multi-edges and self-loops — more than one edge between the same pair of vertices, or an
edge from a vertex to itself — are meaningful in some models. Graphs that allow these are
called multigraphs; the definition used in this course, which does not allow them, is a
**simple graph**.

## Questions Asked with Graphs

As much as the structure itself, the questions asked on it are standard:

- **Reachability:** Is there a path between two vertices?
- **Shortest path:** If one exists, which is the cheapest?
- **Connected components:** How many pieces is the graph split into?
- **Cycle detection:** Does the structure contain a cycle?
- **Ordering:** Is there an execution order consistent with the dependencies?
- **Coverage:** Which set of edges reaches every vertex at the least cost?

Most of these questions require different algorithms depending on whether the graph is
directed and whether it carries weight. The remaining three lessons of this course build
the traversal methods that answer the first four; the shortest-path and coverage
problems, together with the algorithms that bring weights into play, are taken up in the
**Algorithms** course.

## Summary

- A graph is the most general relationship model, made of vertices and edges.
- An undirected edge shows a mutual relationship, a directed edge a one-way one; in a
  directed graph, in-degree and out-degree are separated.
- Weight carries the cost of a relationship and changes what "shortest path" means.
- A tree is an acyclic, connected graph; forests and rooted trees are specialized forms
  of this definition.
- Directed acyclic graphs are the natural model of dependency relationships.
- The sum of degrees is twice the number of edges; edge count is bounded by the square
  of vertex count.

## Next Step

The concept of a graph has been defined, but not how it is kept in memory. The choice is
not trivial: the same algorithm runs at different costs depending on the representation.
The next lesson takes up the two basic representations and the criterion that decides
between them.