Directed and Undirected Graphs

Graphs are one of the most fundamental and expressive data structures in computer science and mathematics. Unlike linear structures such as arrays or linked lists, or hierarchical structures such as trees, a graph can represent virtually any kind of relationship between objects — whether that relationship is symmetric or one-sided, simple or complex, sparse or densely connected. Understanding graphs begins with a precise definition and then broadens into the rich landscape of directed and undirected variants, each with its own structural rules, properties, and real-world domains of application.

A graph G is formally defined as G = (V, E), where V is a finite, non-empty set of vertices (also called nodes) and E is a set of edges that encode relationships between pairs of vertices. A vertex represents an entity — a person, a city, a web page, a task — and an edge represents some meaningful connection or relationship between two such entities. The power of the graph model lies in its generality: by choosing appropriate vertices and edges, you can model an extraordinary range of real-world problems and reason about them using a unified body of theory and algorithms.

For example, consider a small graph with four vertices and four edges:

V = { A, B, C, D }
E = { (A, B), (A, C), (B, D), (C, D) }

This graph captures that A is connected to B and C, and that both B and C are connected to D. Depending on whether those edges carry a direction, this same structure could represent very different real-world situations — a symmetric road network or an asymmetric dependency chain. That distinction is precisely what separates undirected graphs from directed graphs.

Undirected graphs are graphs in which every edge is inherently bidirectional. When we write an edge as the pair (A, B), we mean simultaneously that A is connected to B and B is connected to A. There is no source and no target — the relationship is symmetric by definition. Visually, undirected edges are drawn as plain lines without arrowheads. The most natural way to think about an undirected edge is as a two-way street: if you can drive from city A to city B along that road, you can equally drive from B to A.

A central property of every vertex in an undirected graph is its degree, which is the total number of edges incident to (touching) that vertex. If vertex A participates in three edges, its degree is 3. A useful identity called the Handshaking Lemma states that the sum of all vertex degrees equals exactly twice the number of edges, because every edge contributes one to the degree of each of its two endpoints:

Sum of all degrees = 2 × |E|

This has immediate practical consequences: the sum of degrees in any undirected graph is always even, so a graph can never have an odd number of vertices with odd degree. Understanding vertex degrees helps in tasks such as detecting Eulerian paths and identifying highly connected hub nodes in a network.

Undirected graphs are the natural model whenever a relationship is mutual — when the fact that A relates to B automatically implies that B relates to A. Common examples include:

• Friendship networks on platforms like Facebook, where if Alice is friends with Bob, Bob is equally friends with Alice. Each user is a vertex and each friendship is an undirected edge.
• Road maps where every road segment permits travel in both directions. Intersections become vertices and road segments become undirected edges. Shortest-path algorithms on such maps rely on this symmetry.
• Computer network topologies where an Ethernet cable or wireless link between two machines supports bidirectional communication. Network reliability analysis, bandwidth planning, and fault detection all leverage the undirected graph model.
• Collaboration and co-authorship networks, where two researchers share an undirected edge if they have co-authored a paper. Community detection algorithms use such graphs to find clusters of closely collaborating scientists.

Directed graphs, commonly called digraphs, introduce directionality to edges. An edge in a directed graph is an ordered pair (A, B), meaning there is a directed connection from A to B. This does not imply the existence of an edge from B to A. Visually, directed edges are drawn as arrows. The vertex A is called the tail or source of the edge, and B is called the head or target.

Because edges carry direction, each vertex in a directed graph has two distinct degree measures:

• In-degree: the number of edges arriving at the vertex (edges for which this vertex is the target). A high in-degree indicates that many other nodes point to this one — a property exploited by Google's PageRank algorithm, where a web page with many incoming links is considered authoritative.
• Out-degree: the number of edges departing from the vertex (edges for which this vertex is the source). A high out-degree indicates that this node references or leads to many others.

Consider the following directed graph:

V = { A, B, C, D }
E = { (A, B), (A, C), (B, D), (C, B) }

In-degrees:  A=0, B=2, C=1, D=1
Out-degrees: A=2, B=1, C=1, D=0

Here, A has no incoming edges but two outgoing ones, while D has one incoming edge but no outgoing edges. Such structural analysis is essential for topological sorting: in dependency resolution, vertices with in-degree zero are the ones with no prerequisites and can be processed first.

Directed graphs are the natural model whenever a relationship is asymmetric — when A relating to B does not necessarily mean B relates to A. Common examples include:

• The World Wide Web: each web page is a vertex, and each hyperlink is a directed edge pointing from the linking page to the linked page. A page may be linked to by thousands of others while itself linking to only a handful. Web crawlers traverse this directed graph, and search engine ranking algorithms exploit its structure.
• Task scheduling and build systems: in a software build system such as Make or Gradle, tasks are vertices and a directed edge from task A to task B means "A must be completed before B begins." The build system performs a topological sort of this directed acyclic graph (DAG) to determine a valid execution order. Cycles in this graph represent impossible dependency loops, which the system must detect and reject.
• Social follower relationships on platforms like Twitter or Instagram: user A can follow user B without B following A back. The directed edge (A, B) means "A follows B." Algorithms for finding influencers (high in-degree nodes), detecting echo chambers, and recommending accounts all operate on this directed structure.
• Citation networks: in academic literature, a paper that cites another paper creates a directed edge. Because time flows forward, a paper cannot cite a future paper, making the citation graph a DAG — a fact used in algorithms for measuring academic influence.

The table below summarizes the key structural differences between undirected and directed graphs side by side:

One subtle but important distinction concerns counting edges. In an undirected simple graph on n vertices, the maximum number of edges is n(n−1)/2, because each unordered pair of distinct vertices can appear at most once. In a directed simple graph on the same n vertices, the maximum number of edges is n(n−1), because the ordered pairs (A, B) and (B, A) are counted separately and both may exist simultaneously. This means a directed graph can encode up to twice as much pairwise relationship information as its undirected counterpart on the same vertex set.

The directionality of a graph also has deep implications for connectivity. In an undirected graph, a graph is simply called connected if there exists a path between every pair of vertices. In a directed graph, stronger distinctions apply: a digraph is strongly connected if for every ordered pair (A, B) there exists a directed path from A to B and a directed path from B to A. It is weakly connected if the underlying undirected version (obtained by ignoring edge directions) would be connected. Many real-world directed graphs — such as the web graph — are not strongly connected but do contain large strongly connected components, groups of pages that can mutually reach one another via hyperlinks.

Finally, the choice between directed and undirected representation directly affects which algorithms are applicable and how they behave. Cycle detection differs: in an undirected graph, any back edge encountered during a depth-first search (DFS) reveals a cycle, whereas in a directed graph, only back edges — edges pointing to an ancestor in the DFS tree — signal a directed cycle (cross edges and forward edges do not). Topological sorting is defined only for directed acyclic graphs and has no meaningful counterpart in undirected graphs. Shortest path algorithms such as Dijkstra's operate similarly in both, but directed graphs allow one-way constraints that undirected graphs cannot express. Choosing the right graph type at the outset of problem modeling is therefore not merely a cosmetic decision — it determines the entire algorithmic toolkit available to solve the problem.