Graph Theory Primer (Spring, 2013)

Prepared by:

Joseph Malkevitch
Department of Mathematics
York College (CUNY)
Jamaica, New York 11451

email:

malkevitch@york.cuny.edu

web page:

http://york.cuny.edu/~malk

Graph theory can be thought of as the part of geometry concerned with properties of diagrams consisting of dots and lines (which can be curved or straight). The subject has its origins with the work of Leonard Euler in 1736 but most of the progress in graph theory has come about in the last 70 years. Samples of graphs appear below, and a very brief description of its basic terminology is illustrated using one sample diagram. Lengths of the line segments are not important. This is non-metrical geometry.

----------------------------------------------------------------------------------------------------------------------------------------------------------------

The valence or degree of a vertex is the number of "local" line segments at the vertex. Vertex w has valence 5, vertex v valence 3, and vertex u has valence 4.