Euler Graphs

Consider the following road map

The explorer's Problem: An explorer wants to explore all the routes between a number of cities. Can a tour be found which traverses each route only once? Particularly, find a tour which starts at A, goes along each road exactly once, and ends back at A. Examples of such tour are

A B C D E F B G C E G F A A F G C D E G B C E F B A
The Explorer travels along each road (edges) just once but may visit a particular city (vertex) several times.

The Traveler's Problem

A traveler wants to visit a number of cities. Can a tour be found which visits each city only once? Particularly, find a tour which starts at A, goes to each city exactly once, and ends back at A. Examples of such tour are

A B C D E G F A A F E D C G B A
The travelers visits each city (vertex) just once but may omit several of the roads (edges) on the way.

Eulerian Trail
A connected graph G is Eulerian if there is a closed trail which includes every edge of G, such a trail is called an Eulerian trail.

Hamiltonian Cycle

A connected graph G is Hamiltonian if there is a cycle which includes every vertex of G; such a cycle is called a Hamiltonian cycle. Consider the following examples:

This graph is BOTH Eulerian and Hamiltonian.

This graph is Eulerian, but NOT Hamiltonian.

This graph is an Hamiltionian, but NOT Eulerian.

This graph is NEITHER Eulerian NOR Hamiltionian

Theorem Let G be a connected graph. Then G is Eulerian if and only if every vertex of G has even degree.

Necessary Condition If G is Eulerian, then every vertex of G has even degree. Sufficient Condition If every vertex of G has even degree, then G is Eulerian.

Eulerian-Type Problems Edge-traceable graphs.

 Diagrams-Tracing Puzzles. Dominoes. Mazes and labyrinths, The Chinese Postman Problem. The Rotating Drum Problem. Neither necessary nor sufficient condition is known for a graph to be Hamiltonian. The search for necessary or sufficient conditions is a major area of study in graph theory today.

Sufficient Condition Dirac's Theorem Let G be a simple graph with n vertices where n 3 If deg(v) 1/2 n for each vertex v, then G is Hamiltonian.
For example,

n = 6 and deg(v) = 3 for each vertex, so this graph is Hamiltonian by Dirac's theorem.

Ore's Theorem Let G be a simple graph with n vertices where n 2 if deg(v) + deg(w) n for each pair of non-adjacent vertices v and w, then G is Hamiltonian.
For example,

n = 5 but deg(u) = 2, so Dirac's theorem does not apply. However, deg(v) + deg(w) 5 for all pairs of vertices v and w (infact, for all pairs of vertices v and w), so this graph is Hamiltonian by Ore's theorem.

Note that if deg(v) 1/2 n for each vertex, then deg(v) + deg(w) n for each pair of vertices v and w. It follows that Dirac's theorem can be deduced from Ore's theorem, so we prove only Ore's threoem.

Definitions and Examples

Informally, a graph is a diagram consisting of points, called vertices, joined together by lines, called edges; each edge joins exactly two vertices. A graph G is a triple consisting of a vertex set of V(G), an edge set E(G), and a relation that associates with each edge two vertices (not necessarily distinct) called its endpoints.

Definition of Graph
A graph G = (V, E) consists of a (finite) set denoted by V, or by V(G) if one wishes to make clear which graph is under consideration, and a collection E, or E(G), of unordered pairs {u, v} of distinct elements from V. Each element of V is called a vertex or a point or a node, and each element of E is called an edge or a line or a link. Formally, a graph G is an ordered pair of dsjoint sets (V, E), where E V V. Set V is called the vertex or node set, while set E is the edge set of graph G. Typically, it is assumed that selfloops (i.e. edges of the form (u, u), for some u V) are not contained in a graph.

Directed and Undirected Graph

A graph G = (V, E) is directed if the edge set is composed of ordered vertex (node) pairs. A graph is undirected if the edge set is composed of unordered vertex pair.

Vertex Cardinality
The number of vertices, the cardinality of V, is called the order of graph and devoted by |V|. We usually use n to denote the order of G. The number of edges, the cardinality of E, is called the size of graph and denoted by |E|. We usually use m to denote the size of G.

Neighbor Vertex and Neighborhood

We write vivj E(G) to mean {vi, vj} E(G), and if e = vi vj E(G), we say vi and vj are adjacent. Formally, given a graph G = (V, E), two vertices vi , vj V are said to be neighbors, or adjacent nodes, if ( vi , vj ) E. If G is directed, we distinguish between incoming neighbors of vi (those vertices vj V such that (vj, vi) E) and outgoing neighbors of vi (those vertices vj V such that (vi, vj) E). The open neighborhood N(v) of the vertex v consists of the set vertices adjacent to v, that is, N(v) = {w v : vw E}. The closed neighborhood of v is N[v] = N(v) {v}. For a set S V, the open neighborhood N(S) is defined to be UvSN(v), and the closed neighborhood of S is N[S] = N(S) S.

Vertex Degree

The degree deg(v) of vertex v is the number of edges incident on v or equivalently, deg(v) = | N(v)|. The degree sequence of graph is (deg(v1), deg(v2), ..., deg(vn)), typically written in nondecreasing or nonincreasing order. The minimum and maximum degree of vertices in V(G) are denoted by (G) and (G), respectively. If (G) = (G) = r, then graph G is said to be regular of degree r, or simply r-regular. Formally, given a graph G = (V, E), the degree of a vertex v V is the number of its neighbors in the graph. That is, deg(v) = | {u V : (v, w) E}|. If G is directed, we distinguish between in-degree (nimber of incoming neighbors) and out-degree (number of outgoing neighbors) of a vertex.

Loop and Multiple Edges

A loop is an edge whose endpoints are equal i.e., an edge joining a vertex to it self is called a loop. We say that the graph has multiple edges if in the graph two or more edges joining the same pair of vertices.

Simple Graph
A graph with no loops or multiple edges is called a simple graph. We specify a simple graph by its set of vertices and set of edges, treating the edge set as a set of unordered pairs of vertices and write e = uv (or e = vu) for an edge e with endpoints u and v.

When u and v are endpoints of an edge, they are adjacent and are neighbors.

Connected Graph
A graph that is in one piece is said to be connected, whereas one which splits into several pieces is disconnected.

A graph G is connected if there is a path in G between any given pair of vertices, otherwise it is disconnected. Every disconnected graph can be split up into a number of connected subgraphs, called components.

Subgraph
Let G be a graph with vertex set V(G) and edge-list E(G). A subgraph of G is a graph all of whose vertices belong to V(G) and all of whose edges belong to E(G). For example, if G is the connected graph below:

where V(G) = {u, v, w, z} and E(G) = (uv, uw, vv, vw, wz, wz} then the following four graphs are subgraphs of G.

Degree (or Valency)

Let G be a graph with loops, and let v be a vertex of G. The degree of v is the number of edges meeting at v, and is denoted by deg(v). For example, consider, the following graph G

The graph G has deg(u) = 2, deg(v) = 3, deg(w) = 4 and deg(z) = 1.

Regular Graph
A graph is regular if all the vertices of G have the same degree. In particular, if the degree of each vertex is r, the G is regular of degree r.

The Handshaking Lemma In any graph, the sum of all the vertexdegree is equal to twice the number of edges. Proof
Since each edge has two ends, it must contribute exactly 2 to the sum of the degrees. The result follows immediately. The Following are the consequences of the Handshaking lemma. 1. In any graph, the sum of all the vertex-degree is an even number. 2. In any graph, the number of vertices of odd degree is even. 3. If G is a graph which has n vertices and is regular of degree r, then G has exactly 1/2 nr edges.

Isomorphic Graphs
Two graph G and H are isomorphic if H can be obtained from G by relabeling the vertices - that is, if there is a one-to-one correspondence between the vertices of G and those of H, such that the number of edges joining any pair of vertices in G is equal to the number of edges joining the corresponding pair of vertices in H. For example, two unlabeled graphs, such as

are isomorphic if labels can be attached to their vertices so that they become the same graph.

The word isomorphic derives from the Greek for same and form.

Walk
A walk of length k in a graph G is a succession of k edges of G of the form uv, vw, wx, . . . , yz.

We denote this walk by uvwx . . yz and refer to it as a walk between u and z.

Trail and Path

If all the edges (but no necessarily all the vertices) of a walk are different, then the walk is called a trail. If, in addition, all the vertices are difficult, then the trail is called path.

The walk vzzywxy is a trail since the vertices y and z both occur twice.

The walk vwxyz is a path since the walk has no repeated vertices.

Complete Graphs
A computer graph is a graph in which every two distinct vertices are joined by exactly one edge. The complete graph with n vertices is denoted by Kn. The following are the examples of complete graphs.

The graph Kn is regular of degree n-1, and therefore has 1/2n(n-1) edges, by consequence 3 of the handshaking lemma.

Null Graphs
A null graphs is a graph containing no edges. The null graph with n vertices is denoted by Nn. The following are the examples of null graphs.

Note that Nn is regular of degree 0.

Cycle Graphs
A cycle graph is a graph consisting of a single cycle. The cycle graph with n vertices is denoted by Cn. The following are the examples of cyclic graphs.

Note that Cn is regular of degree 2, and has n edges.

Path Graphs
A path graph is a graph consisting of a single path. The path graph with n vertices is denoted by Pn. The following are the examples of path graphs.

Note that path graph, Pn, has n-1 edges, and can be obtained from cycle graph, Cn, by removing any edge.

Bipartite Graphs
A bipartite graph is a graph whose vertex-set can be split into two sets in such a way that each edge of the graph joins a vertex in first set to a vertex in second set. The examples of bipartite graphs are:

Complete Bipartite Graph

A complete bipartite graph is a bipartite graph in which each vertex in the first set is joined to each vertex in the second set by exactly one edge. The complete bipartite graph with r vertices and 3 vertices is denoted by Kr,s. The following are some examples.

Note that Kr,s has r+s vertices (r vertices of degrees, and s vertices of degree r), and rs edges. Note also that Kr,s = Ks,r. An Important Note: A complete bipartite graph of the form Kr,s is called a star graph.

Cube Graph
The cube graphs is a bipartite graphs and have appropriate in the coding theory. The cube graphs constructed by taking as vertices all binary words of a given length and joining two of these vertices if the corresponding binary words differ in just one place. The binary words of length k is called the k-cube (or k-dimensional cube) graph and is denoted by Qk. The following are some examples.

Note that Qk has 2k vertices and is regular of degree k. It follows from consequence 3 of the handshaking lemma that Qk has k* 2k-1 edges.

The Peterson Graph

This graph is named after a Danish mathematician, Julius Peterson(1839-1910), who discovered the graph in a paper of 1898.

Tree Graph
A tree is a connected graph which has no cycles.

Spanning Tree
If G is a connected graph, the spanning tree in G is a subgraph of G which includes every vertex of G and is also a tree. Consider the following graph

The following are the three of its spanning trees:

Interval Graphs
Consider the intervals (0, 3), (2, 7), (-1, 1), (2, 3), (1, 4), (6, 8) which may be illustrated as

We can construct the resulting interval graphs by taking the interval as vertices, join two of these vertices by an edge whenever the corresponding intervals have at least one point in common.

Note that since the intervals (-1, 1) and (1, 4) are open intervals, they do not have a point in common.

Definition of Diagraph
A directed graph or diagraph D consists of a set of elements, called vertices, and a list of ordered pairs of these elements, called arcs. The set of vertices is called arcs. The set of vertices is called the vertex-set of D, denoted by V(D), and the list of arcs is called the arc-list of D, denoted by A(D). If v and w are vertices of D, then an arc of the form vw is said to be directed from v to w, or to join v to w.

The underlying graph of diagraph is the graph obtained by replacing each arc of diagraph by corresponding (undirected) edge. For example, consider the following digraph

The underlying graph of the above digraph is

The Platonic Graphs

The following regular solids are called the Platonic solids:

Tetrahedron

Hexahedron (cube)

Octahedron

Dodecahedron

Icosahedron The name Platonic arises from the fact that these five solids were mentioned in Plato's Timaeus. A Platonic graph is obtained by projecting the corresponding solid on to a plane.

Connectivity
Bridge
A bridge is a single edge whose removal disconnects a graph.

The above graph G1 can be split up into two components by removing one of the edges bc or bd. Therefore, edge bc or bd is a bridge.

The above graph G2 can be disconnected by removing a single edge, cd. Therefore, edge cd is a bridge.

The above graph G3 cannot be disconnected by removing a single edge, but the removal of two edges (such as ac and bc) disconnects it.

The above graph G4 can be disconnected by removing two edges such as ac and dc.

Edge Connectivity The edge-connectivity (G) of a connected graph G is the smallest number of edges whose removal disconnects G. When (G) k, the graph G is said to be k-edge-connected.
For example, the edge connectivity of the above four graphs G1, G2, G3, and G4 are as follows: G1 has edge-connectivity 1. G2 has edge connectivity 1. G3 has edge connectivity 2. G4 has edge connectivity 2.

Cut Set
A cut set of a connected graph G is a set S of edges with the following properties

The removal of all edges in S disconnects G. The removal of some (but not all) of edges in S does not disconnects G.

As an example consider the following graph

We can disconnect G by removing the three edges bd, bc, and ce, but we cannot disconnect it by removing just two of these edges. Note that a cut set is a set of edges in which no edge is redundant.

Vertex Connectivity
The connectivity (or vertex connectivity) K(G) of a connected graph G (other than a complete graph) is the minimum number of vertices whose removal disconnects G. When K(G) k, the graph is said to be k-connected (or k-vertex connected). When we remove a vertex, we must also remove the edges incident to it. As an example consider following graphs.

The above graph G can be disconnected by removal of single vertex (either b or c). The G has connectivity 1.

The above graph G can be disconnected by removal of single vertex (either c or d). The vertex c or d is a cut-vertex. The G has connectivity 1. g46.gif

The above G can be disconnected by removing just one vertex i.e., vertex c. The vertex c is the cut-vertex. The G has connectivity 1.

The above G cannot be disconnected by removing a single vertex, but the removal of two nonadjacent vertices (such as b and c) disconnects it. The G has connectivity 2.

Cut-Vertex
A cut-vertex is a single vertex whose removal disconnects a graph. It is important to note that the above definition breaks down if G is a complete graph, since we cannot then disconnects G by removing vertices. Therefore, we make the following definition.

Connectivity of Complete Graph

The connectivity k(kn) of the complete graph kn is n-1. When n-1 k, the graph kn is said to be kconnected.

Vertex-Cut set
A vertex-cut set of a connected graph G is a set S of vertices with the following properties. a. the removal of all the vertices in S disconnects G. b. the removal of some (but not all) of vertices in S does not disconnects G. Consider the following graph

We can disconnects the graph by removing the two vertices b and e, but we cannot disconnect it by removing just one of these vertices. the vertex-cutset of G is {b, e}. Note that the connectivity k(G) does not exceed the edge-connectivity (G). This inequality holds for all connected graph. Formally, for any connected graph G we have

K(G) (G) (G)

where (G) is the smallest vertex-degree in G. But it is certainly possible for both inequality in above theorem to be strict inequalities (that is, k(G) < (G) < (G)) For example, in the following graph,

K(G)=1, (G) = 2, and (G) = 3.

Trees
An acyclic graph (also known as a forest) is a graph with no cycles. A tree is a connected acyclic graph. Thus each component of a forest is tree, and any tree is a connected forest.

Theorem

The following are equivalent in a graph G with n vertices.

i. G is a tree. ii. There is a unique path between every pair of vertices in G. iii. G is connected, and every edge in G is a bridge. iv. G is connected, and it has (n - 1) edges. v. G is acyclic, and it has (n - 1) edges. vi. G is acyclic, and whenever any two arbitrary nonadjacent vertices in G are joined by and edge, the resulting enlarged graph G' has a unique cycle. vii.G is connected, and whenever any two arbitrary nonadjacent vertices in G are joined by an edge, the resulting enlarged graph has a unique cycle. Generally speaking, algorithms associated with trees can be divided into three types. Algorithms for searching and labeling a given tree. Algorithms for constructing various types of tree. Algorithms for counting trees of a particular type.

Tree

A tree is a connected graph which contain no cycles.

For example,

Theorem Let T be a graph with n vertices. Then the following statements are equivalent.
a. T is connected and contains no cycles. b. T is connected and has n-1 edges. c. T has n-1 edges and contains no cycles. d. T is connected and each edge is abridge. e. Any two vertices of T are connected by exactly one path. f. T contains no cycles, but the addition of any new edge creates exactly one cycles.

Spanning Trees
Let G be a connected graph. A spanning tree in G is a subgraph of G that includes all the vertices of G and is also a tree. The edges of the trees are called branches. For example, consider the following graph G

The three spanning trees G are:

We can find a spanning tree systematically by using either of two methods. Cutting-down Method Start choosing any cycle in G. Remove one of cycle's edges.

Repeat this procedure until there are no cycle left.

For example, given the graph G

1. We remove the edge ac which destroy the cycle adca in the above graph and we get

2. We remove the edge cb, which destroy the cycle adcba in the above graph and we get

3. We remove the edge ec, which destroy the cycle decd in the above graph and thus obtained the following spanning tree.

Building-up Method Select edges of G one at a time. in such a way that no cycles are created. Repeat this procedure until all vertices are included. For example, for the following graph G

1. Choose the edge ab

2. Next choose the edge de as follows:

3. After that choose the edge ec as follows:

4. Finally, we choose the edge cb and thus obtain the following spanning tree.

Theorem

A graph is connected if and only if it has a spanning tree.

Proof

Let G be a connected graph. Delete edges from G that are not bridges until we get a connected subgraph H in which each edge is a bridge. Then H is a spanning tree. On the other hand, if there is a spanning tree in G, there is a path between any pair of vertices in G; thus G is connected.

Centers and Bicenters

It is convenient to start building up the tree at the middle of a tree and move outwards. This was the approach used by Arthur Cayley when he counted the number of chemical molecules by building them step by step. But what do we mean by the "middle" of a tree? There are two straight forward ways to compute centers and bicenters.

Algorithm1 Remove all the vertices of degree1, together with their incident edges. Repeat the process until we obtain either a single vertex (the center) or two vertices joined by an edge (the bicenter).
A tree with a center is called a central tree, and a tree with a bicenter is called a bicentral tree. Note that every tree is either central or bicentral, but not both. For example, given a following tree.

Remove all vertices of degree 1.

Remove all vertices of degree 1. Therefore, a tree is central with center e.

Another example, given a following tree.

Remove all vertices of degree 1.

Remove all vertices of degree 1.

Therefore, a given tree is bicentral with bicenter cd.

Algorithm 2
For each vertex v of the degree 2 or more, count the number of vertices in each of the subtrees emanating from v, and let nv be the maximum of these numbers. If the tree has n vertices it can be shown that either there is just one vertex v for which nv 1/2(n-1) (the centroid or centroid tree) or there are two adjacent vertices v and w for which nv = nw = 1/2n (the bicentroid or bicentroid tree). It is easy to see that every tree is either centroidal or bicentroidal, but not both. Note that we can think of the centroid or bicentroid as the 'center of gravity' of the tree. For example, given a following tree

Since nc = 4, ne = 4, nf = 5 and ng = 6. Therefore, we have a bicentroidal tree with bicentroid ce.

Another example, given a following tree.

Since nb = 6, nc = 5, nd = 3 and nf = 5. Therefore, we have a centroidal tree with centroid d.

Tree Searching There are two well-known search methods. They are brown as depth-first search( DFS) and breadth-first search (BFS). Each of these methods lists the vertices as they are encountered, and indicates the direction in which each edge is first traversed. The methods differ only in the way in which the vertex-lists are constructed.

Depth-First Search (DFS)

The basic idea of depth-first search is to penetrate as deeply as possible into a tree before fanning out to other vertices. This idea may be depicted as follows:

a -> b --> d --> i -> j -> k -> e -> c -> f -> i -> g -> h. Another example, the expression a + {(b-c) d} can represented by following tree:

Example: Consider the graph

Note that we have marked those edges we used when going to new vertex. These edges form a spanning tree, called a DFS spanning tree.

Breadth-First Search (BFS)

The basic idea of breadth-first search is to fan out to as many vertices as possible before penetrating deep into a tree. This idea may be depicted as follows:

a --> b --> c --> d --> e --> f --> g --> h --> i --> j --> k --> e above example clearly shows that breadth-first search must complete each level before proceeding to the next one. Example: Consider the graph

Note that we have marked those edges we used when going to new vertex. These edges form a spanning tree, called a BFS spanning tree.

Graph Planarity
A graph G is planar if it can be drawn in the plane in such a way that no two edges meet each other except at a vertex to which they are incident. Any such drawing is called a plane drawing of G. For example, the graph K4 is planar, since it can be drawn in the plane without edges crossing.

The three plane drawings of K4 are:

The five Platonic graphs are all planar.

On the other hand, the complete bipartite graph K3,3 is not planar, since every drawing of K3,3 contains at least one crossing. why? because K3,3 has a cycle which must appear in any plane drawing. To study planar graphs, we restrict ourselves to simple graphs.

 If a planar graph has multiple edges or loops. Collapse the multiple edges to a single edge. Remove the loops. Draw the resulting simple graph without crossing. Insert the loops and multiple edges.

Remove loops and multiple edge.

Draw without multiple edge.

Insert loops and multiple edges.

Euler's Formula
If G is a planar graph, then any plane drawing of G divides the plane into regions, called faces. One of these faces is unbounded, and is called the infinite face. If f is any face, then the degree of f (denoted by deg f) is the number of edges encountered in a walk around the boundary of the face f. If all faces have the same degree (g, say), the G is face-regular of degree g. For example, the following graph G has four faces, f4 being the infinite face.

It is easy to see from above graph that deg f1=3, deg f2=4, deg f3=9, deg f4=8. Note that the sum of all the degrees of the faces is equal to twice the number of edges in the the graph , since each edge either borders two different faces (such as bg, cd, and cf) or occurs twice when walk around a single face (such as ab and gh). The Euler's formula relates the number of vertices, edges and faces of a planar graph. If n, m, and f denote the number of vertices, edges, and faces respectively of a connected planar graph, then we get n-m+f = 2. The Euler formula tells us that all plane drawings of a connected planar graph have the same number of faces namely, 2+m-n.

Theorem 1 (Euler's Formula) Let G be a connected planar graph, and let n, m and f denote, respectively, the numbers of vertices, edges, and faces in a plane drawing of G. Then n - m + f = 2. Proof
We employ mathematical induction on edges, m. The induction is obvious for m=0 since in this case n=1 and f=1. Assume that the result is true for all connected plane graphs with

fewer than m edges, where m is greater than or equal to 1, and suppose that G has m edges. If G is a tree, then n=m+1 and f=1 so the desired formula follows. On the other hand, if G is not a tree, let e be a cycle edge of G and consider G-e. The connected plane graph G-e has n vertices, m-1 edges, and f-1 faces so that by the inductive hypothesis,

n - (m - 1) + (f - 1) = 2
which implies that

n - m + f = 2.
We can obtains a number of useful results using Euler's formula. (A "corollary" is a theorem associated with another theorem from which it can be easily derived.)

Corollary 1 Let G be a connected planar simple graph with n vertices, where n 3 and m edges. Then m 3n - 6. Proof
For graph G with f faces, it follows from the handshaking lemma for planar graph that 2m 3f (why?) because the degree of each face of a simple graph is at least 3), so f 2/3 m. Combining this with Euler's formula

Since

n-m+f =2 We get m - n + 2 2/3 m Hence m 3n - 6.

As an example of Corollary 1, show that K5 is non-planar. Proof Suppose that K5 is a planar graph. Since K5 has 5 vertices and 10 edges it follows from
Corollary 1 that 10 (3 5) - 6 = 9. This contradiction shows that K5 is non planar. It is important to note that K3,3 has 6 vertices and 9 edges, and it is true that 9 (3 6) - 6 = 12. This fact simply shows that we cannot use Corollary 1 to prove that K3,3 is non-planar. This leads us to following corollary.

Corollary 2 Let G be a connected planar simple graph with n vertices and m edges, and no triangles. Then m 2n - 4.
Proof For graph G with f faces, it follows from the handshaking lemma for planar graphs that 2m 4f (why because the degree of each face of a simple graph without triangles is at least 4), so that f 1/2 m. Combining this with Euler's formula

Since n-m+f=2 Implies m -n + 2 = f We get m - n + 2 1/2m Hence m 2n - 4 As an example of Corollary 2, show that K3,3 is non-planar. Proof Suppose that K3,3 is a planar graph. Since K3,3 has 6 vertices and 9 edges and no

triangles, it follows from Corollary 2 that 9 (26) - 4 = 8. This contradiction shows that K3,3 is non-planar.

Corollary 3 Let G be a connected planar simple graph. Then G contains at least one vertex of degree 5 or less. Proof From Corollary 1, we get m 3n-6. Suppose that every vertex in G has degree 6 or
more. Then we have 2m 6n (why? because 2m is the sum of the vertex-degree), and therefore m3n. This contradiction shows that at least one vertex has degree 5 or less. Now we will show by using Euler's formula that there are only five regular convex polyhedra namely, the tetrahedron, cube, octahedron, dodecahedron, and isosahedron.

Theorem 2 There are only 5 regular convex polyhedra. Proof We prove this theorem by showing that there are only 5 connected planar graph G with
following properties. i. G is regular of degree d, where d3. ii. Any plane drawing of G is face-regular of degree g where g3. Let n, m and f be the numbers of vertices, edges, and faces of such a planar graph G. Then, from properties (i) and (ii), we ge

m = 1/2 dn
This gives us Therefore, Which can be written as Since 1/m > 0, it follows that

n = 2m/d

and

= 1/2 gf f = 2m/g

Here Euler's formula (n - m + f = 2) holds, since G is a planar graph.

2m/d - m + 2m/g = 2 - 1/2 + 1/g = 1/m 1/d + 1/g > 1/2

1/d

Note that each of d and g is at least 3, so each of 1/d and 1/g is at most 1/3. Therefore, 1/d > 1/2 - 1/3 = 1/6 and 1/g > 1/2 and we conclude that

- 1/3 = 1/6.

d<6

and

g < 6.

This means that the only possible values of d and g are 3, 4, and 5. However, if both d and g are greater than 3, then

1/d + 1/g 1/4 + 1/4 = 1/2

which is a contradiction. This leaves us with just five cases:

Case 1:

When d = 3 and g = 3. we get 1/m = 1/3 - 1/2 + 1/3 = 1/6 Therefore m = 6 It follows that n = 8 and f = 4 and this gives the Tetrahedron. Case 2: When d = 3 and g = 4. we get 1/m = 1/3 - 1/2 + 1/4 = 1/12 Therefore m = 12 It follows that n = 8 and f = 6 and this gives the Cube. Case 3: When d = 3 and g = 5. we get 1/m = 1/3 - 1/2 + 1/5 = 1/30 Therefore m = 30 It follows that n = 20 and f = 12 and this gives the Dodecahedron. Case 4: When d = 4 and g = 3. we get 1/m = 1/4 - 1/2 + 1/3 = 1/12 Therefore m = 12 It follows that n = 6 and f = 8 and this gives the Octahedron. Case 5: When d = 5 and g = 3. we get 1/m = 1/5 - 1/2 + 1/3 = 1/30 Therefore m = 30 It follows that n = 12 and f = 20 and this gives the Icosahedron.

And this completes the proof. Planarity Testing

The Corollaries 1, 2 and their generalization are often useful for showing that graph is not planar. Unfortunately, there are many graphs which satisfy these inequalities but are not planar. Therefore, we need other way to decide planarity. Some important observations: Observation 1 Not all graphs are planar.

For example, we know K5 and K3,3 are not planar.

Observation 2 If G is a planar graph, then every subgraph of G is planar; We usually stated observation 2 as follows Observation 2a

If G contains a nonplanar graph as a subgraph, then G is non-planar. For example, following graph is nonplanar

Since it contains K5 as a subgraph.

The following graph is also non-planar

Since the it contains K3,3 as a subgraph.

Observation 3 If G is a planar graph, then every subdivsion of G is planar, we usually stated observation 3 in the following way. Observation 3a If G is a subdivision of a non-planar graph, then G is non-planar. For example, following graph is non-planar,

Since it is a subdivision of K5.

Also, the following graph is non-planar,

Since it is a subdivision of K3,3.

It follows from observations (2a) and (3a) that, if any graph G contains a subdivision of K5 and K3,3 as a subgraph, then G must be non-planar.

Why are we so obsessed with K5 and K3,3? The reason is that all nonplanar graphs can be obtained by adding vertices and edges to a subdivision of K5 and K3,3. Every non-planar graph contains K5 or K3,3 as a subgraph.

Following result is due to the Polish mathematician K. Kuratowski.

Theorem 3 A graph is planar if and only if it does not contain a subdivision of K5 and K3,3 as a subgraph. Graph Contraction
In the following figure contradiction is done by bringing the vertex w closer and closer to v until w and v coincide and then coalescing multiple edges into a single edge.

Bring vertex w closer to v.

Coalesce vertex v and vertex w.

Finally, coalesce multiple edges and we have

A contraction of a graph is the result of a sequence of edge-contractions. For example, K5 is a contraction of the Petersen graph

Theorem 4 A graph is planar if and only if it does not contain a subgraph which has K5 and K3,3 as a contraction.
The basic idea to test the planarity of the given graph is if we are able to spot a subgraph which is a subdivision of K5 or K3,3 or a subgraph which contracts to K5 or K3,3 then a given graph is non-planar. Theorems 3 and 4 give us necessary and sufficient conditions for a graph to be planar in purely graph-theoretic sense (subgraph, subdivision, K3,3, etc) rather than geometric sense (crossing, drawing in the plane, etc). This is the reason, why there exists no algorithm uses these two theorems for testing the planarity of a graph. Since this would involve looking at a large number of subgraph and verifying that none of them is a subdivision of, or contracts toK5 or K3,3.

Duality
Given a connected planar graph G, we construct dual graph G* in three stages. Take a plane drawing of G. Choose one point inside each face of the plane drawing - these points are the vertices of G*. For each e of the plane drawing, draw a line connecting the vertices of G* on each side of e. This procedure is illustrated as follows:

Note that each plane drawing of G given rise to just one dual graph G*.

Following theorem illustrates a simple relationship between the number of vertices, faces and edges of a graph and its dual.

Theorem 6 If G is a connected planar graph with n vertices, f faces and m edges, then G* has f vertices, n faces and m edges.
In the above example, G has 5 vertices, 4 faces and 7 edges, and G* has 4 faces, 5 faces, and seven edges. Note that if G is a connected planar graph, then G* is also connected planar graph.

Graph Embedding

In this section we introduce the best known parameter involving nonplanar graphs. On a sphere we placed a number of handles or equivalently, inserted a number of holes, so that we can draw a graph with edgecrossings. The number of handles (or holes) is referred to as the genus of the surface and denoted as of or g(G) or gen(G). By the genus, g, of a graph G is meant the smallest genus of all surfaces on which G can be embedded. Every graph has a genus; in fact a graph of size m can be embedded on a surface of genus m. Since the embedding of graphs on spheres and places is equivalent (we can puncture the sphere and get plane), the graphs of genus 0 are precisely the planar graphs. The graph with genus 1 are therefore the nonplanar graphs that are embeddable on the torus. The (nonplanar) graphs K5 and K3,3 have genus 1. Embeddings of K3,3 and K5 on the torus are shown below. Diagram Genus of a Graph The term "planar" comprises two conditions. A graph is planar if It is drawn without edge-crossings It is drawn in a plane.

The concept "genus" includes the first condition but generalizes the seconds by considering other surfaces. The first four members of an infinite family of surfaces i.e., sphere, one-hole torus, two-hole torus, and threehole torus are shown below

These surfaces are taken to be hollow and of negligible thickness. For example, we should think of S0 as a beachball rather than a baseball and of S1 as a valueless inner-tube rather than a doughnut. In the names of the surfaces subscripts refer to the number of holes. Thus, S0 is a "torus" with no holes, S1 is a one-hole torus, S100 is a hundred-hole torus, etc. Definition The genus of a graph, denoted "g" is the subscript on the first surface among the family of surfaces, S0, S1, . . . on which the graph can be drawn without edge-crossings. In this definition we implicitly assumes that every graph has a geuns; That is, given any complicated nonplanar graph G, we can systematically search a

sequence S0, S1, S2, . . . that reveal some surfaces on which G can be drawn without edge-crossing. The genus, g, is just the subscript of the first surface. Theorem 1 The set of all planar graphs is equal to the set of all graphs with g=0. Proof Idea Here we have two statements to establish. First, "Every planar graph has g=o" and second "Every graph with g=0 is planar." To prove that two sets are equal we have to show that each is a subset of the other. This theorem shows that the "planar" concept is merely a special case of the "genus" concept. Planar graphs are the graphs of genus 0. Note that despite of the fact that edges can go "around the back" of a sphere, we cannot avoid edge-crossings on spheres when they cannot be avoided in a plane. Example1. K4 has g = 0 because it is a planar.

Example 2. Each cyclic graph, Cv, has g=0 because it is planar.

Example 3. The complete bipartite graph K3,3 (utility graph) has g=1 because it is nonplanar and so by theorem 1 cannot be drawn without edge-crossings on S0;

but it can be drawn without edge-crossings on S1 (one-hole torus or doughnut).

Thus, the subscript 1 in the is S1 the first surface (doughnut) in the family S0, S1, . . . on which k3,3 can be drawn without edge-crossings. Similarly, K5 has g=1 for the same reasons see the following figure.

Theorem 2

Every graph has a genus.

Proof Let G be any graph. If G is planar it has g=0 by Theorem 1, so let us assume that G is nonplanar. Take a drawing of G in a plane and transfer to the surface of S0. Add to S0 enough "handle" to serve as "overpass", thereby eliminating the edge-crossings. This has been shown in the following figure for K6.

K6 on Surface S0

K6 on Surface S0 with three handles (or holes). Let the number of handles be n. The number n is finite, as a graph can have only finite number of edges and hence only a finite number of edge-crossings. Topologically, the surface consisting S0 of with n handles can be "continuously deformed" into Sn and the edges and vertices of G can be carried along with this continuous deformation. Following figure shows this for S0 with three handles (k6 have been omitted).

Thus G can be drawn on Sn without edge-crossings. Since there is at least one member, Sn, of the sequence of surfaces S0, S1, S2 on which G can be drawn without edge-crossings, there must be a first such number Sg. Then by definition g is the genus of G and we have the theorem. Theorem 3 which ng. If a graph G has genus g then G can be drawn without edge-crossings on every surface Sn for

For specific graph G, its genus g cuts the sequence S0, S1, . . . into two pieces. The first part S0, S1, . . . Sg-1 is finite and consists of all surfaces in the family on which G cannot be drawn without edge-crossings. The second part Sg, Sg+1, . . . is infinite and consists of all surfaces on which G can be drawn without edgecrossings. The "genus" is use to specify the extent to which nonplanar graph is "nonplanar". For example a graph of genus 100 is much farther from planarity than a graph of genus 4.

Up to now the term "face" has been defined only for planar graphs (see Planar Graphs). To speak of the "faces" of say, complete bipartite graph, would have been to speak nonsense. But with new family of surfaces it is now possible to define the term "face" for any graph as follows: If a graph G of genus g has been drawn on the surface of Sg without edge-crossings, then the edges and vertices of G divide the surface of Sg into regions faces of G. Example k3,3 has f=3. Edit --> Include faces> Include faces > Now that "face" makes sense for nonplanar graphs as well, we revisit the Euler formula. Euler's Second Formula For every connected graph of genus g, v + f - e = 2 - 2g It is easy to see that for planar graphs this reduces to the v+f-e=2 Our proof of the Euler's second formula is based on the following assumption that we shall not prove. Assumption If G is a connected graph of genus g then there exists a crossing-free drawing of G on Sg such that through each of the g holes of Sg there is a ring composed of vertices and edges of G. Here are some examples that make us feel that the assumption is at reasonable. Example 1 Consider a drawing of k5 on S1. fig 133 (a) pp. 149 The walk BCDB goes around through the hole and back again. To make a perfect ring out of walk BCDB, the vertices and edges have been rearranged < fig 133(b) > Example Consider the drawing of k3,3 on S1. Again we have walk, XAYBX, that goes around through the hole. < fig 134-a > And again, to make a perfect ring, the vertices and edges have been arranged. < fig. 134-b > Our assumption is that a similar phenomenon occurs for any connected graph. This assumption is reasonable. If G has genus g then G cannot be drawn without edge-crossings on any surfaces having fewer then g holes, so each of the g holes is crucial to waking a crossing-free drawing of G. Therefore, at least one edge of G n=must pass through each hole. Euler's Second Formula If G is connected then n - m + f = 2 - 2g. Proof Some Consequences of Euler's Second Formula Lemma 21. If a connected graph G has n3 and genus g then g (1/6)e - (1/2)(n-2) Proof By the lemma we have 3f 2n. Since G is connected Euler's second formula applies and we have n - m + f = 2 - 2g. Rewritten f = -n + m + 2 -2g multiply by 3

3f = -3n + 3m + 6 -6g Combining with the inequality, 3f 2n. -3n + 3m + 6 - 6g 2n which can be rewritten as -6g -m + 3n - 6 multiply by -1/6 given g (1/6)m -(1/2)(n-2) Using the theorem We can find a lower bound for the genus of a connected graph, even if we know nothing more than its cardinality of vertices and edges. For example, consider the graph with 52 vertices and 201 edges. Then by the theorem we have g (1/6)201 -(1/2)50 = 81/2. But g is an integer so we can conclude that the genus of G is at least 9. The next theorem can be used to find an upper bound for the genus of a graph. Lemma 22. If a graph H of genus gH can be drawn on Sn without edge-crossing, then gHn. Lemma 22c. If H is a subgraph of G, then gHgg. Theorem 22. If n3 the complete graph kn has genus g = left ceiling {(n-3)(n-4)}/12} right ceiling. Corollary 22. If G has n3 and genus g then g left ceiling {(n-3)(n-4)}/12} right ceiling.

The lower and upper bounds for the genus of connected graph, even if we know only its number of vertices, m, and number of edges, n, is as follows left ceiling (1/6)e - (1/2)(v-2) right ceiling g left ceiling{(v-3)(v-4)}/12 right ceiling. Conclusion Euler formula n - m + f = 2 - 2g If G is a connected graph with n3 then g (1/6)m - (1/2)n+1 If G is a connected graph with smallest cycle of length k, then g m/2(1 - (2/k)) - (n/2) g (1/4)m - (1/2)n+1 If G is a graph having blocks B1, B2, . . . , Bk then g = ki=1 g(Bi) A consequence of this result is: If G is a graph with component G1, G2, . . .Gk, then g = ki=1 g(Gi) Computing the genus of Graphs The genus of the complete graph is given by g(kn) = left ceiling {(n-3)(n-4)}/12 right ceiling, n 3. The genus of the complete bipartite graph is given by 1 If G is a connected, triangle-free graph with n3, then

g(kr,s) = left ceiling {(r-2)(s-2)/4}right ceiling, r,s 2. The genus of the n-cube is given by G(Qn) = (n-4). 2n-3 + 1, n 2

Graph Coloring
Vertex Coloring
Let G be a graph with no loops. A k-coloring of G is an assignment of k colors to the vertices of G in such a way that adjacent vertices are assigned different colors. If G has a k-coloring, then G is said to be k-coloring, then G is said to be k-colorable. The chromatic number of G, denoted by X(G), is the smallest number k for which is k-colorable. For example,

3-coloring

4-coloring

5-coloring

Not a permissible coloring, since one of the edge has color blue at both ends. It is easy to see from above examples that chromatic number of G is at least 3. That is X(G) 3, since G has a 3-coloring in first diagram. On the other hand, X(G) 3, since G contains three mutually adjacent vertices (forming a triangle)., which must be assigned different colors. Therefore, we have X(G) = 3.

Lower Bound of X(G)

To obtain a lower bound for X(G), we look for the largest complete subgraph in G. For example, consider the following graph.

Since this graph contains the complete graph K4, therefore X(G) 4.

Upper Bound of X(G)

To obtain an upper bound for X(G), we note that if G has n vertices, then X(G) 4. However, this upper bound is very poor and we can improve it if we know the largest vertex-degree in G, which gives us the following theorem.

Theorem 1 If G is a simple graph whose maximum vertex-degree is d, then X(G) d+1. Proof Idea
Mathematical induction on the number of vertices of G.

We can prove the following slightly stronger theorem, which illustrates the same idea.

Brook's Theorem 2 Let G be a connected simple graph whose maximum vertex-degree is d. If G is neither a cycle graph with an odd number of vertices, nor a complete graph, then X(G) d.
To illustrate the use of Brook's theorem, consider graph G.

Since G contains the complete graph K4, so X(G) 4. On the other hand, G satisfies the conditions of Brook's theorem with d=4 and so X(G) 4. It follows from these two pieces of information that X(G) = 4. It is important to note that Brook's theorem does not always give a tight bound. For example, if G is the bipartite graph k1,100, then X(G) = 2, whereas Brook's theorem gives us the upper bound X(G) 100.

Chromatic Polynomials
All known algorithms for finding the chromatic number of a graph are some what inefficient. A good estimation for the chromatic number of given graph involves the idea of a chromatic polynomials. Let G be a simple graph, and let PG(k) be the number of ways of coloring the vertices of G with k colors in such a way that no two adjacent vertices are assigned the same color. The function PG(k) is called the chromatic polynomial of G. As an example, consider complete graph K3 as shown in the following figure.

Then the top vertex can be assigned any of the k colors, the left vertex can be assigned any k-1 colors, and right vertex can be assigned any of the k-2 colors. The chromatic polynomial of K3 is therefore k(k-1)(k-2). The extension of this immediately gives us the following result.

If G is the complete graph Kn, then PG(k) = k(k - 1)(k - 2) . . . (k - n +1).

Edge Colorings
Let G be a graph with no loops. A k-edge-coloring of G is an assignment of k colors to the edges of G in such a way that any two edges meeting at a common vertex are assigned different colors,. If G has a k-edge coloring, then G is said to be k-edge colorable. The chromatic index of G, denoted by X`(G), is the smallest k for which G is k-edge-colorable. For example, consider the following graphs with eight edges:

4-edges-coloring

5-edge-coloring

6-edge-coloring

Not a permissible coloring. Since two of the edges colored blue meet at a common vertex From the above examples, it follows that X`(G) 4, since G has a 4-edge-coloring in figure a (above). On the other hand, X`(G) 4, since G contains 4 edges meeting at a common vertex i.e., a vertex of degree 4, which must be assigned different colors. Therefore, X`(G) = 4.

Lower Bound of X`(G)

To obtain a lower bound for X`(G), we look for the largest vertex-degree, d, in given G, which gives us X`(G) d.

Upper Bound of X`(G)

To obtain an upper bound for X`(G), we note that if G has m edges, then X`(G) m. However, this upper bound is very poor and has been improved by V. G. Vizing and C. E. Shannon.

Vizing's Theorem 4 If G is a simple graph whose maximum vertexdegree is d, then D X`(G) d+1. Following two theorems give upper bounds for the chromatic index of a graph with multiple edges. Vizing's Theorem for Multiple Edges If G is a graph whose maximum vertex-degree is d, and if h is the maximum number of edges joining a pair of vertices, then d X`(G) d+h.
For example, consider the following graph in which d = 6 and h = 3.

Therefore bounds are 6 X`(G) 9. In fact, X`(G) = 8 for this particular graph.

Shannon's Theorem If G is a graph whose maximum vertex-degree is d, then d X`(G) 3/2 d.

For example, consider the following graph we have d = 6, and so bounds are 6 X`(G) 9. If d is odd, then (3/2)d is not an integer. In which case we can strengthen the bound to (3/2)d - 1/2.

We consider this section with an important theorem by Hungarian mathematician Denes Konig.

Konig's Theorem If G is n bipartite graph whose maximum vertex degree is d, then X`(G) = d. Proof Idea
Mathematical induction on the number of edge of G.

Konig's theorem tells us that every bipartite graph (not necessarily simple) with maximum vertexdegree d can be edge-colored with just d colors.