Graph Theory

How to contact me.
Why I don't want to talk about: Goldbach's Conjecture

Index, Brief History, Basic Definitions


If you have a graph theory page, let me know and I might include a link to it from my page for links to other people's files. I won't usually link to commercial pages.
Please note also: I have received requests for assistance on problems that are standard undergraduate exercises. The most I will do in these situations is point out the exercise in a standard text (in case the writer doesn't realize that it is a standard problem) or refer the writer to a chapter in a standard textbook.

Very Brief History

The earliest paper on graph theory seems to be by Leonhard Euler, Solutio problematis ad geometriam situs pertinentis, Commetarii Academiae Scientiarum Imperialis Petropolitanae 8(1736), 128-140. Euler discusses whether or not it is possible to stroll around Konigsberg (later called Kaliningrad) crossing each of its bridges across the Pregel (later called the Pregolya) exactly once. Euler gave the conditions which are necessary to permit such a stroll.

Thomas Pennyngton Kirkman (1856) and William Rowan Hamilton (1856) studied trips which visited certain sites exactly once.

Graph Theory was born to study problems of this type. For much more on the history of graph theory, I suggest the book
Graph Theory 1736-1936, by N.L. Biggs, E.K. Lloyd and R.J. Wilson.

Example of a Graph

The World Wide Web is an example of a (directed) graph. The files are the vertices. A link from one file to another is a directed edge (or arc).

Why Did I Start This?

These pages were started as I taught a graduate course in Graph Theory (Spring 1996). My favourite text, Bondy and Murty, was out of print. My second choice was also out of print. Of course, I always want to do things which are slightly different than are covered in a textbook anyway.

Who could resist using the web to pass along information? I am trying, for the most part, to write these pages from memory. Some material was taken very directly from a course that Herb Shank taught at Waterloo, c. 1974. Bruce Richter was going to put those notes into a monograph for Herb, but that hasn't materialized. I've listed the unsolved problems from Appendix IV of Bondy and Murty.

In Spring 1997, I used West as the course text (and that now has a second edition). I hear that Chartrand and Lesniak had a new edition.

These pages are not intended to replace the standard texts in Graph Theory, rather to give a place on the web where some of the basic definitions can be found. I doubt if they will ever be as complete as a text can be. On the other hand, I am not constrained by an editor (just by the lack of symbols in html -- and that will change one day), so I can include almost anything. You won't find any graphics here. They take up too much space. (But I might learn JAVA.)

Students in the (Spring 1996) course were expected to take notes, draw pictures of graphs, read some of the standard texts, etc. Also, I have not tried to attribute every result to the researcher who produced the result - some standard texts do this and some don't. If I don't point out a result as being mine, then it almost certainly isn't.

The last third of the (Spring 1996) course was comprised of student presentations from the literature.

I do think the web might eventually replace the idea of textbooks. Direct linking to definitions and other theorems is more pleasant than searching for page references. There is a Yahoo site just for Mathematics courses. (You may have gotten here from there.)


Basic Definitions

A simple graph can be thought of as a triple G=(V,E,I), where V and E are disjoint finite sets and I is an incidence relation such that every element of E is incident with exactly two distinct elements of V and no two elements of E are incident to the same pair of elements of V. Obviously, these requirements can be varied (and we get
general graphs, hypergraphs, infinite graphs, directed graphs, oriented graphs, etc.). We call V the vertex set and E the edge set of G.

The degree, d(v), of a vertex v is the number of edges with which it is incident. Two vertices are adjacent if they are incident to a common edge. The set of neighbours, N(v), of a vertex v is the set of vertices which are adjacent to v. The degree of a vertex is also the cardinality of its neighbour set.

A walk is an alternating sequence of vertices and edges, with each edge being incident to the vertices immediately preceeding and succeeding it in the sequence. A trail is a walk with no repeated edges. A path is a walk with no repeated vertices. A walk is closed if the initial vertex is also the terminal vertex. A cycle is a closed trail with at least one edge and with no repeated vertices except that the initial vertex is the terminal vertex.

The length of a walk is the number of edges in the sequence defining the walk. Thus, the length of a path or cycle is also the number of edges in the path or cycle. If u and v are vertices, the distance from u to v, written d(u,v), is the minimum length of any path from u to v. In an undirected graph, this is obviously a metric. The eccentricity, e(u), of the vertex u is the maximum value of d(u,v), where v is allowed to range over all of the vertices of the graph. The radius of the graph G, rad(G), is the minimum value of e(u), for any vertex u, and the diameter, diam(G), is the corresponding maximum value. It should be obvious that diam(G) ≤ 2rad(G).

For a set of vertices X, we use G[X] to denote the
induced subgraph of G whose vertex set is X and whose edge set is the subset of E(G) consisting of those edges with both ends in X. For a set S of edges, we use G[S] to denote the edge induced subgraph of G whose edge set is S and whose vertex set is the subset of V(G) consisting of those vertices incident with any edge in S. If Y is a subset of V(G), we write G-Y for the subgraph G[V(G)-Y]. A graph is complete, or a clique, if every pair of distinct vertices is adjacent. (The adjacency matrix of a complete graph has zeroes on the main diagonal, and ones off the diagonal.) We write Km for the complete graph on m vertices.

A non-null graph is connected if, for every pair of vertices, there is a walk whose ends are the given vertices. Let us write u~v if there is path from u to v. Then ~ is an equivalence relation. The equivalence classes under ~ are the vertex sets of the connected components of G. A connected graph is therefore a graph with exactly one connected component. A non-complete graph G is k-connected if for every proper subset Y of V(G) with fewer than k elements, G-Y is connected. A graph G has connectivity k if G is k-connected but not (k+1)-connected. A complete graph on k+1 vertices is defined to have connectivity k. See Dirac's Theorem and Menger's Theorem.


Index

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

Acyclic

Automorphism Group

Back to the top of the Index


Bandwidth

Bicentral Tree

Binding Number

Bond Space

Bound δ (of a graph embedded in on a surface)

Back to the top of the Index


Cage

Center

Central Tree

Characteristic Polynomial

Chromatic Polynomial

Clique (complete graph)

Colourings

Cocycle Space

2-Commondity Flows

Connected

k-Connected

Connectivity

Contractions and Deletions

Corank

Coxeter graph

Crosscap (of a non-orientable surface)

Cubic (3-regular)

Cycle

Cycle Double Cover

Cycle Space

Back to the top of the Index


Decomposition into Paths of Length Two

Degree

Diameter

diconnected

Dirac's Theorems

Distance

Back to the top of the Index


Eccentricity

Edge Induced Subgraphs

Edge Transitive

Embeddings on a surface

Euler Characteristic of a surface

Euler' Theorem (generalized to surfaces)

Euler's Theorem (via cycle space)

Back to the top of the Index


Factors

5-Flow Conjecture

Forests

Back to the top of the Index


Girth

Graceful Labellings

Back to the top of the Index


Handle (of an orientable surface)

Heawood's Colouring Theorem (surfaces)

Heuristics (Colouring)

Back to the top of the Index


Idiosyncratic Polynomial

Induced Subgraphs

Isomorphism and Matrices

Isomorphism Testing (General)

Isomorphism Testing (Trees)

Back to the top of the Index


Kuhn-Menkres Algorithm (Matchings)

Back to the top of the Index


Length

Linear Spaces Associated with a Graph

Back to the top of the Index


Matrix Tree Theorem

Matroids (Base B, Circuit C, Closure s, Greedy G, Independence I, Rank r, Rank r')

Menger's Theorems

Minors

Back to the top of the Index


Neighbour

Back to the top of the Index


Pancyclic

Path

3-Path-Transitive

Perfect Graphs; Perfect graph pages by V. Chvátal

Petersen graph

Planar

Platonic solids

Back to the top of the Index


Radius

Ramsey Numbers

Rank

Rank Polynomial

Reconstruction

Back to the top of the Index


(Some) Standard Texts

Back to the top of the Index


Toughness

Tournament

Trail

Trees

Tutte Polynomial

Back to the top of the Index


Unsolved Problems

Back to the top of the Index


Vertex Transitive

Back to the top of the Index


Walk

Back to the top of the Index


This page can now be reached from Yahoo.
Department of Mathematical Sciences
Florida Atlantic University
777 Glades Road
Boca Raton, Florida 33431-0991
USA

Office: Room 286, Science & Engineering
Phone: (561) 297-3350
Fax: (561) 297-2436
URL: http://www.math.fau.edu/locke/graphthe.htm


Last modified September 1, 2000, by S.C. Locke.