Graph terminology

A graph consists of nodes and edges. In this book, the variable $n$ denotes the number of nodes in a graph, and the variable $m$ denotes the number of edges. The nodes are numbered using integers $1,2,\ldots,n$.

For example, the following graph consists of 5 nodes and 7 edges:

A path leads from node $a$ to node $b$ through edges of the graph. The length of a path is the number of edges in it. For example, the above graph contains a path $1 \rightarrow 3 \rightarrow 4 \rightarrow 5$ of length 3 from node 1 to node 5:

A path is a cycle if the first and last node is the same. For example, the above graph contains a cycle $1 \rightarrow 3 \rightarrow 4 \rightarrow 1$. A path is simple if each node appears at most once in the path.

Connectivity

A graph is connected if there is a path between any two nodes. For example, the following graph is connected:

The following graph is not connected, because it is not possible to get from node 4 to any other node:

The connected parts of a graph are called its components. For example, the following graph contains three components: {$1,2,3$}, {$4,5,6,7$} and {$8$}.

A tree is a connected graph that consists of $n$ nodes and $n-1$ edges. There is a unique path between any two nodes of a tree. For example, the following graph is a tree:

Edge directions

A graph is directed if the edges can be traversed in one direction only. For example, the following graph is directed:

The above graph contains a path $3 \rightarrow 1 \rightarrow 2 \rightarrow 5$ from node $3$ to node $5$, but there is no path from node $5$ to node $3$.

Edge weights

In a weighted graph, each edge is assigned a weight. The weights are often interpreted as edge lengths. For example, the following graph is weighted:

The length of a path in a weighted graph is the sum of the edge weights on the path. For example, in the above graph, the length of the path $1 \rightarrow 2 \rightarrow 5$ is $12$, and the length of the path $1 \rightarrow 3 \rightarrow 4 \rightarrow 5$ is $11$. The latter path is the \key{shortest} path from node $1$ to node $5$.

Neighbors and degrees

Two nodes are neighbors or adjacent if there is an edge between them. The degree of a node is the number of its neighbors. For example, in the following graph, the neighbors of node 2 are 1, 4 and 5, so its degree is 3.

The sum of degrees in a graph is always $2m$, where $m$ is the number of edges, because each edge increases the degree of exactly two nodes by one. For this reason, the sum of degrees is always even.

A graph is regular if the degree of every node is a constant $d$. A graph is complete if the degree of every node is $n-1$, i.e., the graph contains all possible edges between the nodes.

In a directed graph, the indegree of a node is the number of edges that end at the node, and the outdegree of a node is the number of edges that start at the node. For example, in the following graph, the indegree of node 2 is 2, and the outdegree of node 2 is 1.

Colorings

In a coloring of a graph, each node is assigned a color so that no adjacent nodes have the same color.

A graph is bipartite if it is possible to color it using two colors. It turns out that a graph is bipartite exactly when it does not contain a cycle with an odd number of edges. For example, the graph

is bipartite, because it can be colored as follows:

However, the graph

is not bipartite, because it is not possible to color the following cycle of three nodes using two colors:

Simplicity

A graph is simple if no edge starts and ends at the same node, and there are no multiple edges between two nodes. Often we assume that graphs are simple. For example, the following graph is not simple: