# Discrete Mathematics/Graph theory

## Introduction

editA *graph* is a mathematical way of representing the concept of a "network".

A network has points, connected by lines. In a graph, we have special names for these. We call these points *vertices* (sometimes also called nodes), and the lines, *edges*.

Here is an example graph. The edges are red, the vertices, black.

In the graph, are vertices, and are edges.

## Definitions of graph

editThere are several roughly equivalent definitions of a **graph**. Set theory is frequently used to define graphs. Most commonly, a graph is defined as an ordered pair , where is called the graph's **vertex-set** and is called the graph's **edge-set**. Given a graph , we often denote the vertex—set by and the edge—set by . To visualize a graph as described above, we draw dots corresponding to vertices . Then, for all we draw a line between the dots corresponding to vertices if and only if there exists an edge . Note that the placement of the dots is generally unimportant; many different pictures can represent the same graph.

Alternately, using the graph above as a guide, we can define a graph as an ordered triple :

- a set of vertices, commonly called V
- a set of edges, commonly called E
- a relation that maps to each edge a set of
*endpoints*, known as the*edge-endpoint relation*. We say an edge is**incident**to a vertex iff .

In the above example,

- V={v
_{1}, v_{2}, v_{3}, v_{4}} - E={e
_{1}, e_{2}, e_{3}, e_{4}, e_{5}} - f such that e
_{1}maps to {v_{1}, v_{2}}, e_{2}maps to {v_{1}, v_{3}}, e_{3}maps to {v_{1}, v_{4}}, e_{4}maps to {v_{2}, v_{4}}, and e_{5}maps to {v_{3}, v_{4}}.

If is not injective — that is, if such that — then we say that is a **multigraph** and we call any such edges *multiple edges*. Further, we call edges such that **loops**. Graphs without multiple edges or loops are known as **simple graphs**.

Graphs can, conceivably, be infinite as well, and thus we place no bounds on the sets V and E. We will not look at infinite graphs here.

### Directions, Weights, and Flows

editWe define a **directed graph** as a graph such that maps into the set of ordered pairs rather than into the family of two-element sets . We can think of an edge such that as 'pointing' from to . As such we would say that is the *tail* of edge and that is the *head*. This is one of the vagaries of graph theory notation, though. We could just as easily think of as the head and as the tail. To represent a directed graph, we can draw a picture as described and shown above, but place arrows on every edge corresponding to its direction.

In general, a **weight** on a graph is some function .

A **flow** is a directed graph paired with a weight function such that the weight "going into" any vertex is the same amount as the weight "going out" of that vertex. To make this more formal, define sets

Then, formally stated, our requirement on the weight function is

### Algebraic Graph Theory

editWhile set theory is frequently used when discussing graphs, other approaches can simplify certain operations. A set can be defined using an adjacency matrix where element is a 1, if there is an edge between vertex i and vertex j and 0 otherwise.

### Special Graphs

editSome graphs occur frequently enough in graph theory that they deserve special mention. One such graphs is the *complete graph* on n vertices, often denoted by K_{n}. This graph consists of n vertices, with each vertex connected to every other vertex, and every pair of vertices joined by exactly one edge. Another such graph is the *cycle graph* on *n* vertices, for *n* at least 3. This graph is denoted C_{n} and defined by V := {1,2,..,n} and E := {{1,2},{2,3}, ..., {n-1,n},{n,1}}. Even easier is the *null graph* on *n* vertices, denoted N_{n}; it has *n* vertices and no edges! Note that N_{1} = K_{1} and C_{3} = K_{3}.

### Some Terms

editTwo vertices are said to be *adjacent* if there is an edge joining them. The word *incident* has two meanings:

- An edge
*e*is said to be incident to a vertex*v*if*v*is an endpoint of*e*. - Two edges are also incident to each other if both are incident to the same vertex.

Two graphs *G* and *H* are said to be *isomorphic* if there is a one-to-one function from (or, if you prefer, one-to-one correspondence between) the vertex set of *G* to the vertex set of *H* such that two vertices in *G* are adjacent if and only if their images in *H* are adjacent. (Technically, the multiplicity of the edges must also be preserved, but our definition suffices for simple graphs.)

### Subgraphs

editA *subgraph* is a concept akin to the subset. A subgraph has a subset of the vertex set V, a subset of the edge set E, and each edge's endpoints in the larger graph has the same edges in the subgraph. A

A subgraph of is *generated* by the vertices { } if the edge set of consists of all edges in the edge set of that joins the vertices in { }.

A *path* is a sequence of edges such that e_{i} is adjacent to e_{i+1} for all i from 1 to N-1. Two vertices are said to be connected if there is a path connecting them.

## Trees and Bipartite Graphs

editA *tree* is a graph that is (i) connected, and (ii) has no cycles.
Equivalently, a tree is a connected graph with
exactly edges, where there are nodes in the tree.

A *Bipartite graph* is a graph whose nodes can be partitioned into two disjoint
sets U and W such that every edge in the graph is incident to one node in U and one
node in W. A tree is a bipartite graph.

A *complete bipartite graph* is a bipartite graph in which each node in U is connected to every node in W;
a complete bipartite graph in which U has vertices and V has vertices
is denoted .

Adjacent,Incident,End Vertices

Self loops,Parallel edges,Degree of Vertex

Pendant Vertex : Vertex Degree one "Pendant Vertex" Isolated Vertex : Vertex Degree zero "Isolated Vertex"

## Hamiltonian and Eulerian Paths

editHamiltonian Cycles: A Hamiltonian Cycle received its name from Sir William Hamilton who first studied the travelling salesman problem. A Hamiltonian cycle is a path that visits every vertex once and only once i.e. it is a walk, in which no edge is repeated (a trail) and therefore a trail in which no vertex is repeated (a path). Note also it is a cycle, the last vertex is joined to the first.

A graph is said to be Eulerian if it is possible to traverse each edge once and only once, i.e. it has no odd vertices or it has an even number of odd vertices (semi-Eulerian). This has implications for the Königsberg problem. It may be easier to imagine this as if it is possible to trace the edges of a graph with a pencil without lifting the pencil off the paper or going over any lines.

## Planar Graphs

editA *planar graph* is an undirected graph that can be
drawn on the plane or on a sphere in such
a way that no two edges cross,
where an edge is drawn as a continuous curve
(it need not be a straight line) from u to v.

Kuratowski proved a remarkable fact about planar graphs: A graph is planar if and only if it does not contain a subgraph homeomorphic to or to . (Two graphs are said to be homeomorphic if we can shrink some components of each into single nodes and end up with identical graphs. Informally, this means that non-planar-ness is caused by only two things—namely, having the structure of or within the graph).

### Coloring Graphs

editA graph is said to be planar if it can be drawn on a plane in such way that no edges cross one another except of course for meeting at vertices

Each term, the Schedules Office in some university must assign a time slot for each final exam. This is not easy, because some students are taking several classes with finals, and a student can take only one test during a particular time slot. The Schedules Office wants to avoid all conflicts, but to make the exam period as short as possible.

We can recast this scheduling problem as a question about coloring the vertices of a graph. Create a vertex for each course with a final exam. Put an edge between two vertices if some student is taking both courses. For example, the scheduling graph might look like this: Next, identify each time slot with a color. For example, Monday morning is red, Monday afternoon is blue, Tuesday morning is green, etc.

Assigning an exam to a time slot is now equivalent to coloring the corresponding vertex. The main constraint is that adjacent vertices must get different colors; otherwise, some student has two exams at the same time. Furthermore, in order to keep the exam period short, we should try to color all the vertices using as few different colors as possible. For our example graph, three colors suffice: red, green, blue.

The coloring corresponds to giving one final on Monday morning (red), two Monday afternoon (blue), and two Tuesday morning (green)...

### K Coloring

editMany other resource allocation problems boil down to coloring some graph. In general, a graph G is kcolorable if each vertex can be assigned one of k colors so that adjacent vertices get different colors. The smallest sufficient number of colors is called the chromatic number of G. The chromatic number of a graph is generally difficult to compute, but the following theorem provides an upper bound:

Theorem 1. A graph with maximum degree at most k is (k + 1)colorable.

Proof. We use induction on the number of vertices in the graph, which we denote by n. Let P(n) be the proposition that an nvertex graph with maximum degree at most k is (k + 1)colorable. A 1 vertex graph has maximum degree 0 and is 1colorable, so P(1) is true.

Now assume that P(n) is true, and let G be an (n + 1)vertex graph with maximum degree at most k. Remove a vertex v, leaving an nvertex graph G . The maximum degree of G is at most k, and so G is (k + 1)colorable by our assumption P(n). Now add back vertex v. We can assign v a color different from all adjacent vertices, since v has degree at most k and k + 1 colors are available. Therefore, G is (k + 1)colorable. The theorem follows by induction.

## Weighted Graphs

editA **weighted graph** associates a label (weight) with every edge in the graph. Weights are usually real numbers, and often represent a "cost" associated with the edge, either in terms of the entity that is being modeled, or an optimization problem that is being solved.