Chapter 24
Some Examples from Graph Theory
As the title suggests, this chapter will introduce some examples where the Catalan numbers arise in graph theory.
In Chapter 12, we were introduced to the structure called an undirected graph. In our first example, we shall investigate a special collection of undirected graphs, which have no loops and are defined using closed intervals of unit length.
Example 24.1 (Unit-Interval Graphs): For n ≥ 1, we start with n closed intervals of unit length and draw the corresponding unit-interval graphs on n vertices, as shown in Fig. 24.1 (for the cases where n = 1 and n = 2). In Fig 24.1 (a) we find one unit interval. This corresponds to the single (isolated) vertex u1. Here we can represent both the closed interval and the unit-interval graph by the binary string 01. When we consider two closed unit intervals, we can draw them so that they do not overlap, as in Fig. 24.1 (b), or overlapping, as in part (c) of the figure. When two closed unit intervals overlap, we draw an edge in the graph joining the vertices that correspond to the two closed unit intervals. Consequently, the unit-interval graph in Fig. 24.1 (b) consists of the two isolated vertices 
and 
, which correspond respectively with the first and second closed unit intervals that do not ...
