10.1 Graph Terminology and Properties

Graph Fundamentals

Graphs model relationships between entities. A graph consists of vertices (also called nodes) and edges that connect them. This structure is flexible enough to represent social networks, road systems, web pages, task dependencies, and much more.

Understanding graph terminology is the foundation for every graph algorithm you'll encounter later. This section covers the core vocabulary: vertices, edges, degree, and the major graph types.

Graph Fundamentals

Vertices and Edges

A graph has two building blocks:

• Vertices (nodes) represent entities or objects.
• Edges represent relationships or connections between vertices.

Edges come in several flavors depending on the problem you're modeling:

• Weighted edges carry a numerical value representing cost, distance, or strength of a connection (e.g., road distance between two cities).
• Unweighted edges simply indicate that a connection exists, with no associated value.
• Directed edges point from one vertex to another, like a one-way street.
• Undirected edges have no direction and represent a two-way connection.

A single graph can be both directed and weighted, or undirected and unweighted. These properties are independent of each other.

Directed vs. Undirected Graphs

Directed graphs (digraphs) have edges with a specific direction, drawn as arrows. The order of the two vertices matters: an edge from A to B is not the same as an edge from B to A.

Real-world examples:

• Social media followers: an edge from user A to user B means A follows B, but B doesn't necessarily follow A.
• Web page links: an edge from page A to page B means A contains a hyperlink to B.
• Task dependencies: an edge from task A to task B means A must be completed before B can start.

Undirected graphs have edges with no direction. If an edge exists between A and B, you can traverse it both ways.

Real-world examples:

• Friendships on a social network: if A is friends with B, then B is friends with A.
• Road networks (assuming two-way roads): an edge between two cities means you can drive in either direction.
• Collaboration networks: an edge between two researchers means they've co-authored a paper.

Vertex Properties

Degree

The degree of a vertex measures how many edges are connected to it.

In an undirected graph, the degree of a vertex is simply the number of edges incident to it. For example, if vertex C connects to vertices A, B, and D, then C has degree 3.

In a directed graph, degree splits into two counts:

• In-degree: the number of edges pointing into the vertex.
• Out-degree: the number of edges pointing out of the vertex.

The total degree of a vertex in a directed graph equals its in-degree plus its out-degree.

One useful fact: the Handshaking Lemma states that in any undirected graph, the sum of all vertex degrees equals twice the number of edges ($\sum \deg(v) = 2|E|$). This makes sense because each edge contributes 1 to the degree of each of its two endpoints.

Classification of Graph Types

Complete Graphs

A complete graph has an edge between every pair of distinct vertices. If a complete graph has $n$ vertices, the number of edges is:

$\frac{n(n-1)}{2}$

For example, a complete graph on 5 vertices has $\frac{5 \times 4}{2} = 10$ edges. Complete graphs are often denoted $K_n$ (so $K_5$ is the complete graph on 5 vertices).

Bipartite Graphs

A bipartite graph has its vertices split into two disjoint sets, and every edge connects a vertex in one set to a vertex in the other set. No edges exist between vertices within the same set.

Think of it this way: you can color every vertex either red or blue such that no edge connects two vertices of the same color.

Common applications:

• Job assignment: one set is workers, the other is tasks, and edges represent which workers can do which tasks.
• Course enrollment: one set is students, the other is courses, and edges represent who is enrolled in what.

Connected Graphs

An undirected graph is connected if there's a path between every pair of vertices. Starting from any vertex, you can reach every other vertex by following edges.

A graph that isn't connected is called disconnected and breaks into two or more connected components, each of which is a maximal connected subgraph. For directed graphs, the analogous (and stricter) concept is strongly connected, meaning there's a directed path from every vertex to every other vertex.