## Introduction

LOWELL W. BEINEKE and ROBIN J. WILSON

1. Graph theory

2. Graphs in the plane

3. Surfaces

4. Graphs on surfaces

References

### 1. **Graph theory**

This section presents the basic definitions, terminology and notation of graph theory, along with some fundamental results. Further information can be found in the many standard books on the subject – for example, Chartrand and Lesniak [1] , Gross and Yellen [2], West [3] or (for a simpler treatment) Wilson [4].

#### Graphs

A *graph G* is a pair of sets (*V, E*), where *V* is a finite non-empty set of elements called *vertices*, and *E* is a finite set of elements called *edges*, each of which has two associated vertices (which may be the same). The sets *V* and *E* are the *vertex-set* and *edge-set* of *G*, and are sometimes ...