**Path or walk**is a sequence of edges that begins at a vertex of a graph and travels from vertex to vertex along edges of the graph.The path is a

**circuit or closed walk**if it begins and ends at the same vertex. A path or circuit is simple if it does not contain the same edge more than once. A path or circuit is**simple or sometimes called a trail**if it does not contain the same edge more than once.Some books use terminology path for a trail with no repeated vertices

An undirected graph is called

**connected**if there is a path between every pair of distinct vertices of the graph. An undirected graph that is not connected is called disconnected. There is a simple path between every pair of distinct vertices of a connected undirected graphA

**connected component of a graph G**is a connected subgraph of G that is not a proper subgraph of another connected subgraph of G. That is, a connected component of a graph G is a maximal connected subgraph of G.A graph G that is not connected has two or more connected components that are disjoint and have G as their union. The connected components of the graph H are shown below :

Sometimes the removal from a graph of a vertex and all incident edges produces a subgraph with more connected components. Such vertices are called

**cut vertices**(or articulation points). The removal of a cut vertex from a connected graph produces a subgraph that is not connected. Analogously, an edge whose removal produces a graph with more connected components than in the original graph is called a**cut edge or bridge**. Every connected graph, except a complete graph, has a vertex cut.

**Q. ind the cut vertices and cut edges in the graph G _{1} shown below**

The cut vertices of G

_{1}are b, c, and e. The removal of one of these vertices (and its adjacent edges) disconnects the graph.The cut edges are {a, b} and {c, e}.

Removing either one of these edges disconnects G

_{1}.

An

**Euler circuit**in a graph G is a simple circuit containing every edge of G. An**Euler path**in G is a simple path containing every edge of G.If a connected graph has an Euler circuit, then every vertex must have even degree.

A connected multigraph with at least two vertices has an Euler circuit if and only if each of its vertices has even degree.

A connected multigraph has an Euler path but not an Euler circuit if and only if it has exactly two vertices of odd degree.

A simple path in a graph G that passes through every vertex exactly once is called a

**Hamilton path**, and a simple circuit in a graph G that passes through every vertex exactly once is called a**Hamilton circuit**.A graph with a vertex of degree one cannot have a Hamilton circuit, because in a Hamilton circuit, each vertex is incident with two edges in the circuit.

Adding edges (but not vertices) to a graph with a Hamilton circuit produces a graph with the same Hamilton circuit.

A Hamilton circuit cannot contain a smaller circuit within it.

If G is a simple graph with n vertices with n ≥ 3 such that the degree of every vertex in G is at least n/2, then G has a Hamilton circuit.

If G is a simple graph with n vertices with n ≥ 3 such that deg(u) + deg(v) ≥ n for every pair of nonadjacent vertices u and v in G, then G has a Hamilton circuit

A graph is called planar if it can be drawn in the plane without any edges crossing (where a crossing of edges is the intersection of the lines or arcs representing them at a point other than their common endpoint). Such a drawing is called a planar representation of the graph.

All planar representations of a graph split the plane into the same number of regions.

Let G be a connected planar simple graph with e edges and v vertices. Let r be the number of regions in a planar representation of G. Then

**r = e − v + 2**.

**Q. Suppose that a connected planar simple graph has 20 vertices, each of degree 3. Into how many
regions does a representation of this planar graph split the plane?**

This graph has 20 vertices, each of degree 3, so v = 20. Because the sum of the degrees of the vertices, 3v = 3 · 20 = 60, is equal to twice the number of edges, 2e,wehave2e = 60, or e = 30. Consequently, from Euler’s formula, the number of regions is

r = e − v + 2 = 30 − 20 + 2 = 12.

**Theories of Planar Graphs**

If G is a connected planar simple graph with e edges and v vertices, where v ≥ 3, then e ≤ 3v − 6.

If G is a connected planar simple graph, then G has a vertex of degree not exceeding ﬁve.

If a connected planar simple graph has e edges and v vertices with v ≥ 3 and no circuits of length three, then

**e ≤ 2v − 4**.

**Graph Coloring**

A coloring of a simple graph is the assignment of a color to each vertex of the graph so that no two adjacent vertices are assigned the same color.

The chromatic number of a graph is the least number of colors needed for a coloring of this graph. The chromatic number of a graph G is denoted by χ(G). (Here χ is the Greek letter chi.)

**THE FOUR COLOR THEOREM :**The chromatic number of a planar graph is no greater than four.

**Q. Scheduling Final Exams: How can the ﬁnal exams at a university be scheduled so that no
student has two exams at the same time?**

This scheduling problem can be solved using a graph model, with vertices representing courses and with an edge between two vertices if there is a common student in the courses they represent. Each time slot for a ﬁnal exam is represented by a different color. A scheduling of the exams corresponds to a coloring of the associated graph.

For instance, suppose there are seven ﬁnals to be scheduled. Suppose the courses are numbered 1 through 7. Suppose that the following pairs of courses have common students: 1 and 2, 1 and 3, 1 and 4, 1 and 7, 2 and 3, 2 and 4, 2 and 5, 2 and 7, 3 and 4, 3 and 6, 3 and 7, 4 and 5, 4 and 6, 5 and 6, 5 and 7, and 6 and 7. In Figure 8 the graph associated with this set of classes is shown. A scheduling consists of a coloring of this graph.

Because the chromatic number of this graph is 4 (the reader should verify this), four time slots are needed.

Previous | Next |