Discrete Mathematics/Graph theory

Introduction

A 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, $v_{1},v_{2},v_{3},v_{4}$ are vertices, and $e_{1},e_{2},e_{3},e_{4},e_{5}$ are edges.

Definitions of graph

There are several roughly equivalent definitions of a graph. Set theory is frequently used to define graphs. Most commonly, a graph $G$ is defined as an ordered pair $G=(V,E)$, where $V=\{v_{1},\ldots ,v_{n}\}$ is called the graph's vertex-set and $E=\{e_{1},\ldots ,e_{m}\}\subset \{\{x,y\}|x,y\in V\}$ is called the graph's edge-set. Given a graph $G$, we often denote the vertex—set by $V(G)$ and the edge—set by $E(G)$. To visualize a graph as described above, we draw $n$ dots corresponding to vertices $v_{1},\ldots ,v_{n}$. Then, for all $i,j\in \{1,\ldots ,n\}$ we draw a line between the dots corresponding to vertices $v_{i},v_{j}$ if and only if there exists an edge $\{v_{i},v_{j}\}\in E$. 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 $G=(V,E,f)$:

• a set of vertices, commonly called V
• a set of edges, commonly called E
• a relation $f:E\rightarrow \{\{x,y\}|x,y\in V\}$ that maps to each edge a set of endpoints, known as the edge-endpoint relation. We say an edge $e\in E$ is incident to a vertex $v\in V$ iff $v\in f(e)$.

In the above example,

• V={v₁, v₂, v₃, v₄}
• E={e₁, e₂, e₃, e₄, e₅}
• f such that e₁ maps to {v₁, v₂}, e₂ maps to {v₁, v₃}, e₃ maps to {v₁, v₄}, e₄ maps to {v₂, v₄}, and e₅ maps to {v₃, v₄}.

If $f$ is not injective — that is, if $\exists e,e'\in E$ such that $e\neq e',f(e)=f(e')$ — then we say that $G$ is a multigraph and we call any such edges $e,e'\in E$ multiple edges. Further, we call edges $e\in E$ such that $|f(e)|=1$ 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

We define a directed graph as a graph such that $f$ maps into the set of ordered pairs $\{(x,y)|x,y\in V\}$ rather than into the family of two-element sets $\{\{x,y\}|x,y\in V\}$. We can think of an edge $e\in E$ such that $f(e)=(x,y)$ as 'pointing' from $x$ to $y$. As such we would say that $x$ is the tail of edge $e$ and that $y$ is the head. This is one of the vagaries of graph theory notation, though. We could just as easily think of $x$ as the head and $y$ 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 $G$ is some function $c:E(G)\rightarrow \mathbb {R}$.

A flow $(G,c)$ is a directed graph $G=(V,E,f)$ 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

• $f^{+}(v)=\{e\in E(G)|f(e)=(v,x),x\in V(G)\},\;\forall v\in V(G)$
• $f^{-}(v)=\{e\in E(G)|f(e)=(x,v),x\in V(G)\},\;\forall v\in V(G)$

Then, formally stated, our requirement on the weight function is $\sum _{e\in f^{+}(v)}c(e)=\sum _{e\in f^{-}(v)}c(e),\;\forall v\in V(G).$

Algebraic Graph Theory

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

Special Graphs

The complete graph on 6 vertices

Some 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₁ = K₁ and C₃ = K₃.

Some Terms

Two 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

Generated Subgraphs

A 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 $H$ of $G$ is generated by the vertices {$a,b,c,...$}$\in H$ if the edge set of $H$ consists of all edges in the edge set of $G$ that joins the vertices in $H=${$a,b,c,...$}.

A path is a sequence of edges $<e_{1},...,e_{N}>$ 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

A tree is a graph that is (i) connected, and (ii) has no cycles. Equivalently, a tree is a connected graph with exactly $n-1$ edges, where there are $n$ 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 $n$ vertices and V has $m$ vertices is denoted $K_{n,m}$.

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

Hamiltonian 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

A 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 $e=(u,v)$ 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 $K_{5}$ or to $K_{3,3}$. (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 $K_{5}$ or $K_{3,3}$ within the graph).

Coloring Graphs

A 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

Many 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

A 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.