Chapter 12

Examples from Graph Theory: An Introduction to the Lucas Numbers

Let us start with some basic ideas from graph theory.

An undirected graph G is made up of a nonempty set V of vertices and a set E (possibly empty) of edges between the vertices in V. For example, in Fig. 12.1 (a), we have and E = {uv, vw, vv}, where it is understood, for example, that uv = vu. Here we say that , are neighbors and u, are also neighbors—but u, are not neighbors. Also, the edge vv shown in the figure is an example of a loop (at ).

In Fig. 12.1 (b), we have a second undirected graph—this time and E = {uv, vw, ux, xy, yu}. Here the edges ux, xy, and yu constitute a cycle. Since this cycle ...