X

### Connectivity

• 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 graph

• A 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 G1 shown below

• The cut vertices of G1 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 G1.

### Euler Paths and Circuits

• 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

### Planar Graphs

• 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