In **Graph Theory**, a graph is defined to be a set of dots (called vertices or nodes) connected by links (called arcs or edges). A more formal definition is:

A simple graph is a set of nodes *N* and a set *E* of unordered pairs of distinct elements of *N* called *edges*.

1 _____ 2 _____ 3 \ / / \ / / an example of graph with five vertices and six edges \ / / 5 _____ 4

Here, *N* = {1, 2, 3, 4, 5} and *E* = {(1,2), (1,5), (2,3), (2,5), (3,4), (4,5)}.

- adjacent

Two nodes are considered *adjacent* if an edge exists between them. In the above graph, nodes 1 and 2 are adjecent, but nodes 2 and 4 are not.

- neighbor

The set of *neighbors* for a node contains each node adjacent to it. In the above graph, node 1 has two neighbors: node 2 and node 5.

- path

A *path* is a series of nodes in that each node is adjacent to both the preceding and succeding node. A path is considered *simple* if none of the nodes in the path are repeated. In the above graph, {1, 2, 5, 1, 2, 3} is a path, and {5, 2, 1} is a simple path.

If it is possible to establish a path from any vertex to any other vertex of a graph, the graph is said to be *connected*.

- cycle

A *cycle* is a path that begins and ends with the same node. In the above graph, {1, 5, 2, 1} is a cycle. A path is *acyclic* if it is not a cycle.
A *simple cycle* is one in which the beginning node only appears once more, as the ending node.

A connected graph without cycles is said a *tree*; equivalently, a tree on *n* vertices is a connected graph with exactly *n*-1 edges. Trees are largely used as data structures in computer science (see tree data structure).

- complete

A *complete* graph is one in which every node is adjacent to every other node. The above graph is **not** complete. The complete graph on *n* vertices is often denoted by *K _{n}*. It has

- planar

A *planar* graph is one which can be drawn in the plane without any two edges intersecting. The above graph is
planar; the complete graph on *n* vertices, for *n*> 4, is not planar.

**Graph Problems**

- Coloring graphs: the four color theorem

lots more stuff here when I get time!