**Graph Theory**

Network Theory is an application of Graph Theory. We take the term *network *to refer to the informal concept describing an object composed of elements and interactions or connections between these elements.

For example, the Internet is a network composed of nodes (routers, hosts) and connections between these nodes (e.g. fiber cables). The natural means to model networks mathematically is provided by the notion of graphs.

A *graph **G *= (*V,E*) is an abstract object formed by a set *V *of *vertices *(nodes) and a set *E *of edges (links) that join (connect) pairs of vertices. The vertex set and edge set of a graph *G *are denoted by *V *(*G*) and *E*(*G*), respectively. The cardinality of *V *is usually denoted by *n*, the cardinality of *E *by *m*. The two vertices joined by an edge are called its *endvertices*. If two vertices are joined by an edge, they are *adjacent *and we call them *neighbors*.

Graphs can be *undirected *or *directed*. In undirected graphs, the order of the endvertices of an edge is immaterial. An undirected edge joining vertices *u, v **∈* *V *is denoted by *{**u, v**}*. In directed graphs, each directed edge (arc) has an *origin *(*tail*) and a *destination *(*head*). An edge with origin *u **∈* *V *and destination *v **∈* *V *is represented by an ordered pair (*u, v*). As a shorthand notation, an edge *{**u, v**} *or (*u, v*) can also be denoted by *uv*. In a directed graph, *uv *is short for (*u, v*), while in an undirected graph, *uv *and *vu *are the same and both stand for *{**u, v**}*.

For a directed graph *G *= (*V,E*), the *underlying undirected graph *is the undirected graph with vertex set *V *that has an undirected edge between two vertices *u, v **∈* *V *if (*u, v*) or (*v, u*) is in *E*. Graphs that can have directed edges as well as undirected edges are called *mixed graphs*, but such graphs are encountered rarely and we will not discuss them explicitly in the following.