The Concept of a Graph

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.

# 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.