11.3: Some Common Graphs

Some graphs come up so frequently that they have names. A complete graph \(K_n\) has \(n\) vertices and an edge between every two vertices, for a total of \(n(n-1)/2\) edges. For example, \(K_5\) is shown in Figure 11.3.

The empty graph has no edges at all. For example, the empty graph with 5 nodes is shown in Figure 11.4.

Figure 11.3 \(K_5\): the complete graph on 5 nodes.

Figure 11.4 An empty graph with 5 nodes.

An \(n\)-node graph containing \(n_1\) edges in sequence is known as a line graph \(L_n\). More formally, \(L_n\) has

\[\nonumber V(L_n) = \{v_1, v_2, \ldots, v_n\}\]

and

\[\nonumber E(L_n) = \{\langle v_1 - v_2 \rangle, \langle v_2 - v_3 \rangle, \ldots, \langle v_{n-1} - v_n \rangle\}\]

For example, \(L_5\) is pictured in Figure 11.5.

There is also a one-way infinite line graph \(L_{\infty}\) which can be defined by letting the nonnegative integers \(\mathbb{N}\) be the vertices with edges \((k - (k + 1))\) for all \(k \in \mathbb{N}\).

If we add the edge \(\langle v_n - v_1 \rangle\) to the line graph \(L_n\), we get a graph called a length-n cycle \(C_n\). Figure 11.6 shows a picture of length-5 cycle.

Figure 11.5 \(L_5\): a 5-node line graph.

Figure 11.6 \(C_5\): a 5-node cycle graph.