1 of 127

Chapter 10 Graphs

Definition: A graph G = (V, E) consists of a nonempty set V of vertices (or nodes) and a set E of edges. Each edge has either one or two vertices associated with it, called its endpoints. An edge is said to connect its endpoints.

Simple Graph

Multi Graph

Pseudo Graph

Null Graph

Complete Graph

Regular Graph

Basic Types of GRAPH

2 of 127

Some Terminology

In a simple graph each edge connects two different vertices and no two edges connect the same pair of vertices.
Multigraphs may have multiple edges connecting the same two vertices. When m different edges connect the vertices u and v, we say that {u,v} is an edge of multiplicity m.
An edge that connects a vertex to itself is called a loop.
A pseudograph may include loops, as well as multiple edges connecting the same pair of vertices.

Remark: There is no standard terminology for graph theory. So, it is crucial that you understand the terminology being used whenever you read material about graphs.

Example:

This pseudograph has both multiple edges and a loop.

3 of 127

Directed Graphs

Definition: An directed graph (or digraph)�G = (V, E) consists of a nonempty set V of vertices (or nodes) and a set E of directed edges (or arcs). Each edge is associated with an ordered pair of vertices. The directed edge associated with the ordered pair (u,v) is said to start at u and end at v.

Remark:

Graphs where the end points of an edge are not ordered are said to be undirected graphs.

4 of 127

Some Terminology (continued)

A simple directed graph has no loops and no multiple edges.

A directed multigraph may have multiple directed edges. When there are m directed edges from the vertex u to the vertex v, we say that (u,v) is an edge of multiplicity m.

In this directed multigraph the multiplicity of (a,b) is 1 and the multiplicity of (b,c) is 2.

Example:

This is a directed graph with three vertices and four edges.

Example:

5 of 127

Graph Terminology: Summary

To understand the structure of a graph and to build a graph model, we ask these questions:

Are the edges of the graph undirected or directed (or both)?
If the edges are undirected, are multiple edges present that connect the same pair of vertices? If the edges are directed, are multiple directed edges present?
Are loops present?

6 of 127

10.1 Graphs and Graph Models

When we build a graph model, we use the appropriate type of graph to capture the important features of the application.
We illustrate this process using graph models of different types of computer networks. In all these graph models, the vertices represent data centers and the edges represent communication links.
To model a computer network where we are only concerned whether two data centers are connected by a communications link, we use a simple graph. This is the appropriate type of graph when we only care whether two data centers are directly linked (and not how many links there may be) and all communications links work in both directions.

7 of 127

Graph Models: �Computer Networks (continued)

To model a computer network where we care about the number of links between data centers, we use a multigraph.

8 of 127

Graph Models: Computer Networks

To model a computer network with diagnostic links at data centers, we use a pseudograph, as loops are needed.

9 of 127

Graph Models: Computer Networks

To model a network with multiple one-way links, we use a directed multigraph. Note that we could use a directed graph without multiple edges if we only care whether there is at least one link from a data center to another data center.

10 of 127

Graph Models: Social Networks

Graphs can be used to model social structures based on different kinds of relationships between people or groups.
In a social network, vertices represent individuals or organizations and edges represent relationships between them.
Useful graph models of social networks include:

friendship graphs - undirected graphs where two people are connected if they are friends (in the real world, on Facebook, or in a particular virtual world, and so on.)
collaboration graphs - undirected graphs where two people are connected if they collaborate in a specific way
influence graphs - directed graphs where there is an edge from one person to another if the first person can influence the second person..

11 of 127

Graph Models: Social Networks

Example: A friendship graph where two people are connected if they are Facebook friends.

12 of 127

Graph Models: Social Networks

Example: An influence graph

13 of 127

Applications to Information Networks

Graphs can be used to model different types of networks that link different types of information.
In a web graph, web pages are represented by vertices and links are represented by directed edges.

A web graph models the web at a particular time.
We will explain how the web graph is used by search engines in Section 11.4.

In a citation network:

Research papers in a particular discipline are represented by vertices.
When a paper cites a second paper as a reference, there is an edge from the vertex representing this paper to the vertex representing the second paper.

14 of 127

Transportation Graphs

Graph models are extensively used in the study of transportation networks.
Airline networks can be modeled using directed multigraphs where

airports are represented by vertices
each flight is represented by a directed edge from the vertex representing the departure airport to the vertex representing the destination airport

Road networks can be modeled using graphs where

vertices represent intersections and edges represent roads.
undirected edges represent two-way roads and directed edges represent one-way roads.

15 of 127

Software Design Applications

Graph models are extensively used in software design. We will introduce two such models here; one representing the dependency between the modules of a software application and the other representing restrictions in the execution of statements in computer programs.

When a top-down approach is used to design software, the system is divided into modules, each performing a specific task.
We use a module dependency graph to represent the dependency between these modules. These dependencies need to be understood before coding can be done.

16 of 127

Software Design Applications

In a module dependency graph vertices represent software modules and there is an edge from one module to another if the second module depends on the first.

Example: The dependencies between the seven modules in the design of a web browser are represented by this module dependency graph.

17 of 127

Software Design Applications

We can use a directed graph called a precedence graph to represent which statements must have already been executed before we execute each statement.

Vertices represent statements in a computer program
There is a directed edge from a vertex to a second vertex if the second vertex cannot be executed before the first

Example: This precedence graph shows which statements must already have been executed before we can execute each of the six statements in the program.

18 of 127

Biological Applications

Graph models are used extensively in many areas of the biological science. We will describe two such models, one to ecology and the other to molecular biology.
Niche overlap graphs model competition between species in an ecosystem

Vertices represent species and an edge connects two vertices when they represent species who compete for food resources.

Example: This is the niche overlap graph for a forest ecosystem with nine species.

19 of 127

Biological Applications

We can model the interaction of proteins in a cell using a protein interaction network.
In a protein interaction graph, vertices represent proteins and vertices are connected by an edge if the proteins they represent interact.
Protein interaction graphs can be huge and can contain more than 100,000 vertices, each representing a different protein, and more than 1,000,000 edges, each representing an interaction between proteins
Protein interaction graphs are often split into smaller graphs, called modules, which represent the interactions between proteins involved in a particular function.

20 of 127

Biological Applications

Example: This is a module of the protein interaction graph of

proteins that degrade RNA in a human cell.

21 of 127

Graph Terminology�and �Special Types of Graphs

Section 10.2

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

22 of 127

Basic Terminology

Definition 1. Two vertices u, v in an undirected graph G are called adjacent (or neighbors) in G if there is an edge e between u and v. Such an edge e is called incident with the vertices u and v and e is said to connect u and v.

Definition 2. The set of all neighbors of a vertex v of G = (V, E), denoted by N(v), is called the neighborhood of v. If A is a subset of V, we denote by N(A) the set of all vertices in G that are adjacent to at least one vertex in A. So,

Definition 3. The degree of a vertex in a undirected graph is the number of edges incident with it, except that a loop at a vertex contributes two to the degree of that vertex. The degree of the vertex v is denoted by deg(v).

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

23 of 127

Degrees and Neighborhoods of Vertices

Example: What are the degrees and neighborhoods of the vertices in the graphs G and H?

Solution:

G: deg(a) = 2, deg(b) = deg(c) = deg(f ) = 4, deg(d ) = 1, deg(e) = 3, deg(g) = 0.

N(a) = {b, f }, N(b) = {a, c, e, f }, N(c) = {b, d, e, f }, N(d) = {c},

N(e) = {b, c , f }, N(f) = {a, b, c, e}, N(g) = ∅ .

H: deg(a) = 4, deg(b) = deg(e) = 6, deg(c) = 1, deg(d) = 5.

N(a) = {b, d, e}, N(b) = {a, b, c, d, e}, N(c) = {b}, N(d) = {a, b, e},

N(e) = {a, b ,d}.

24 of 127

Handshaking Theorem

Theorem: If G is any graph, then the sum of the degrees of all the vertices of G equals twice the number of edges of G.

COROLLARY: The total degree of G is an even number

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

25 of 127

Example: How many edges are there in a graph with 10 vertices of degree six?

Solution: Because the sum of the degrees of the vertices is 6 ⋅ 10 = 60, the handshaking theorem tells us that 2m = 60. So the number of edges m = 30.

Example: If a graph has 5 vertices, can each vertex have degree 3?

Solution: This is not possible by the handshaking theorem, because the sum of the degrees of the vertices 3 ⋅ 5 = 15 is odd.

Handshaking Theorem

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

26 of 127

Theorms of Graph

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

27 of 127

Degree of Vertices

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

28 of 127

Directed Graphs (continued)

Definition: The in-degree of a vertex v, denoted deg⁻(v), is the number of edges which terminate at v. The out-degree of v, denoted deg⁺(v), is the number of edges with v as their initial vertex. Note that a loop at a vertex contributes 1 to both the in-degree and the out-degree of the vertex.

Example: In the graph G we have

deg⁻(a) = 2, deg⁻(b) = 2, deg⁻(c) = 3, deg⁻(d) = 2, deg⁻(e) = 3, deg⁻(f) = 0.

deg⁺(a) = 4, deg⁺(b) = 1, deg⁺(c) = 2, deg⁺(d) = 2, deg⁺(e) = 3, deg⁺(f) = 0.

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

29 of 127

Special Types of Simple Graphs: �Complete Graphs

A complete graph on n vertices, denoted by K_n, is the simple graph that contains exactly one edge between each pair of distinct vertices.

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

30 of 127

Special Types of Simple Graphs: �Cycles and Wheels

A cycle C_nfor n ≥ 3 consists of n vertices v₁, v₂ ,⋯ , v_n, and edges {v₁, v₂}, {v₂, v₃} ,⋯ , {v_n-₁, v_n}, {v_n, v₁}.

A wheel W_nis obtained by adding an additional vertex to a cycle C_nfor n ≥ 3 and connecting this new vertex to each of the n vertices in C_n by new edges.

31 of 127

Special Types of Graphs and Computer Network Architecture

Various special graphs play an important role in the design of computer networks.

Some local area networks use a star topology, which is a complete bipartite graph K₁_,_n,as shown in (a). All devices are connected to a central control device.
Other local networks are based on a ring topology, where each device is connected to exactly two others using C_n,as illustrated in (b). Messages may be sent around the ring.
Others, as illustrated in (c), use a W_n – based topology, combining the features of a star topology and a ring topology.

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

32 of 127

Special Types of Simple Graphs: �n-Cubes

An n-dimensional hypercube, or n-cube, Q_n, is a graph with 2ⁿ vertices representing all bit strings of length n, where there is an edge between two vertices that differ in exactly one bit position.

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

33 of 127

Special Types of Graphs and Computer Network Architecture

Various special graphs also play a role in parallel processing where processors need to be interconnected as one processor may need the output generated by another.
The n-dimensional hypercube, or n-cube, Qn, is a common way to connect processors in parallel, e.g., Intel Hypercube.
Another common method is the mesh network, illustrated here for 16 processors.

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

34 of 127

Thanks

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

35 of 127

Bipartite Graphs

Definition: A simple graph G is bipartite if V can be partitioned into two disjoint subsets V1 and V2 such that every edge connects a vertex in V1 and a vertex in V2. In other words, there are no edges which connect two vertices in V1 or in V2.

It is not hard to show that an equivalent definition of a bipartite graph is a graph where it is possible to color the vertices red or blue so that no two adjacent vertices are the same color.

What is disjoint Set?

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

36 of 127

Degree of Vertices

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

37 of 127

Bipartite Graphs (continued)

Example: Show that C₃ is not bipartite.

Solution: If we divide the vertex set of C₃ into two nonempty sets, one of the two must contain two vertices. But in C₃ every vertex is connected to every other vertex. Therefore, the two vertices in the same partition are connected. Hence, C₃ is not bipartite.

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

38 of 127

Bipartite Graphs (continued)

Example: Show that C₆ is bipartite.

Solution: We can partition the vertex set into

V₁ = {v₁, v₃, v₅} and V₂ = {v₂, v₄, v₆} so that every edge of C₆ connects a vertex in V₁ and V₂ .

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

39 of 127

Bipartite Graphs

G is bipartite

H is not bipartite since if we color a red, then the adjacent vertices f and b must both be blue.

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

40 of 127

Bipartite graphs are used to model applications that involve matching the elements of one set to elements in another, for example:
Job assignments - vertices represent the jobs and the employees, edges link employees with those jobs they have been trained to do. A common goal is to match jobs to employees so that the most jobs are done.

Bipartite Graphs and Matchings

41 of 127

Complete Bipartite Graphs

Definition: A complete bipartite graph K_m,n is a graph that has its vertex set partitioned into two subsets V₁ of size m and V₂ of size n such that there is an edge from every vertex in V₁ to every vertex in V₂.

Example: We display four complete bipartite graphs here.

42 of 127

New Graphs from Old

Definition: A subgraph of a graph G = (V,E) is a graph (W,F), where W ⊂ V and F ⊂ E. A subgraph H of G is a proper subgraph of G if H ≠ G.

Example: Here we show K₅ and one of its subgraphs.

Definition: Let G = (V, E) be a simple graph. The subgraph induced by a subset W of the vertex set V is the graph (W,F), where the edge set F contains an edge in E if and only if both endpoints are in W.

Example: Here we show K₅and the subgraph induced by W = {a,b,c,e}.

43 of 127

New Graphs from Old (continued)

Definition: The union of two simple graphs G₁ = (V₁, E₁) and G₂ = (V₂, E₂) is the simple graph with vertex set V₁ ⋃ V₂ and edge set E₁ ⋃ E₂. The union of G₁ and G₂ is denoted by G₁ ⋃ G₂.

Example:

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

44 of 127

Section Summary

Adjacency Lists
Adjacency Matrices
Incidence Matrices

Representations of Graphs

Section 10.3

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

45 of 127

Representing Graphs: Adjacency Lists

Definition: An adjacency list can be used to represent a graph with no multiple edges by specifying the vertices that are adjacent to each vertex of the graph.

Example:

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

46 of 127

Representing Graphs: Adjacency Lists

Example:

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

47 of 127

Representation of Graphs:�Adjacency Matrices

Definition: Suppose that G = (V, E) is a simple graph where |V| = n. Arbitrarily list the vertices of G as v₁, v₂, … , v_n. The adjacency matrix A_G of G, with respect to the listing of vertices, is the n × n zero-one matrix with 1 as its (i, j)th entry when v_i and v_j are adjacent, and 0 as its (i, j)th entry when they are not adjacent.

In other words, if the graphs adjacency matrix is A_G= [a_ij], then

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

48 of 127

Adjacency Matrices (continued)

Example:

The ordering

of vertices is a, b, c, d.

The ordering of vertices is a, b, c, d.

Note: The adjacency matrix of a simple graph is symmetric, i.e., a_ij= a_ji

Also, since there are no loops, each diagonal entry a_ij for i = 1, 2, 3, …, n, is 0.

When a graph is sparse, that is, it has few edges relatively to the total number of possible edges, it is much more efficient to represent the graph using an adjacency list than an adjacency matrix. But for a dense graph, which includes a high percentage of possible edges, an adjacency matrix is preferable.

49 of 127

Adjacency Matrices (continued)

Adjacency matrices can also be used to represent graphs with loops and multiple edges.
A loop at the vertex vi is represented by a 1 at the (i, j)th position of the matrix.
When multiple edges connect the same pair of vertices vi and vj, (or if multiple loops are present at the same vertex), the (i, j)th entry equals the number of edges connecting the pair of vertices.
Example: We give the adjacency matrix of the pseudograph shown here using the ordering of vertices a, b, c, d.

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

50 of 127

Representation of Graphs:�Incidence Matrices

Definition: Let G = (V, E) be an undirected graph with vertices where v₁, v₂, … v_n and edges e₁, e₂, … e_m. The incidence matrix with respect to the ordering of V and E is the n × m matrix M = [m_ij], where

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

51 of 127

Incidence Matrices (continued)

Example: Simple Graph and Incidence Matrix

The rows going from top to bottom represent v₁ through v₅ and the columns going from left to right represent e₁ through e₆.

Example: Pseudograph and Incidence Matrix

The rows going from top to bottom represent v₁ through v₅ and the columns going from left to right represent e₁ through e₈.

52 of 127

Connectivity

Section 10.4

53 of 127

Paths

Informal Definition: A path is a sequence of edges that begins at a vertex of a graph and travels from vertex to vertex along edges of the graph. As the path travels along its edges, it visits the vertices along this path, that is, the endpoints of these.

Applications: Numerous problems can be modeled with paths formed by traveling along edges of graphs such as:

determining whether a message can be sent between two computers.
efficiently planning routes for mail delivery.

54 of 127

Paths

Definition: Let n be a nonnegative integer and G an undirected graph. A path of length n from u to v in G is a sequence of n edges e₁, … , e_n of G for which there exists a sequence x₀ = u, x₁, …, x_n-₁, x_n = v of vertices such that e_ihas, for i = 1, …, n, the endpoints x_i_-₁ and x_i.

When the graph is simple, we denote this path by its vertex sequence x₀, x₁, … , x_n(since listing the vertices uniquely determines the path).
The path is a circuit if it begins and ends at the same vertex (u = v) and has length greater than zero.
The path or circuit is said to pass through the vertices x₁, x₂, … , x_n-₁ and traverse the edges e₁, … , e_n.
A path or circuit is simple if it does not contain the same edge more than once.

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

55 of 127

Paths (continued)

Example: In the simple graph here:

a, d, c, f, e is a simple path of length 4.
d, e, c, a is not a path because e is not connected to c.
b, c, f, e, b is a circuit of length 4.
a, b, e, d, a, b is a path of length 5, but it is not a simple path.

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

56 of 127

Summary of WALK TRAIL and PATH

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

57 of 127

Connectedness in Undirected Graphs

Definition: An undirected graph is called connected if there is a path between every pair of vertices. An undirected graph that is not connected is called disconnected. We say that we disconnect a graph when we remove vertices or edges, or both, to produce a disconnected subgraph.

Example: G₁ is connected because there is a path between any pair of its vertices, as can be easily seen. However G₂ is not connected because there is no path between vertices a and f, for example.

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

58 of 127

Connected and Strongly Connected Components� in a Graph

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

59 of 127

Euler and Hamiltonian Graphs

Section 10.5

60 of 127

Section Summary

Euler Paths and Circuits
Hamilton Paths and Circuits
Applications of Hamilton Circuits

Euler and Hamiltonian Graphs

Section 10.5

61 of 127

Euler Graph, Paths and Circuits

The town of Kӧnigsberg, Prussia

(now Kalingrad, Russia) was divided into four sections by the branches of the Pregel river. In the 18th century seven bridges connected these regions.

People wondered whether it was possible to follow a path that crosses each bridge exactly once and returns to the starting point.
The Swiss mathematician Leonard Euler proved that no such path exists. This result is often considered to be the first theorem ever proved in graph theory.

62 of 127

Euler Paths and Circuits

Definition: 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.

Example: Which of the undirected graphs G₁, G₂, and G₃ has a Euler circuit? Of those that do not, which has an Euler path?

Solution: The graph G₁ has an Euler circuit (e.g., a, e, c, d, e, b, a). But, as can easily be verified by inspection, neither G₂ nor G₃ has an Euler circuit. Note that G₃ has an Euler path (e.g., a, c, d, e, b, d, a, b), but there is no Euler path in G₂, which can be verified by inspection.

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

63 of 127

Euler Circuits and Paths

Example:

G₁ contains exactly two vertices of odd degree (b and d). Hence it has an Euler path, e.g., d, a, b, c, d, b.

G₂ has exactly two vertices of odd degree (b and d). Hence it has an Euler path, e.g., b, a, g, f, e, d, c, g, b, c, f, d.

G₃ has six vertices of odd degree. Hence, it does not have an Euler path.

64 of 127

Necessary Conditions for Euler Circuits and Paths

An Euler circuit begins with a vertex a and continues with an edge incident with a, say {a, b}. The edge {a, b} contributes one to deg(a).
Each time the circuit passes through a vertex it contributes two to the vertex’s degree.
Finally, the circuit terminates where it started, contributing one to deg(a). Therefore deg(a) must be even.
We conclude that the degree of every other vertex must also be even.
By the same reasoning, we see that the initial vertex and the final vertex of an Euler path have odd degree, while every other vertex has even degree. So, a graph with an Euler path has exactly two vertices of odd degree.
In the next slide we will show that these necessary conditions are also sufficient conditions.

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

65 of 127

Algorithm for Constructing an Euler Circuits

In our proof we developed this algorithms for constructing a Euler circuit in a graph with no vertices of odd degree.

66 of 127

Applications of Euler Paths and Circuits

Euler paths and circuits can be used to solve many practical problems such as finding a path or circuit that traverses each

street in a neighborhood,
road in a transportation network,
connection in a utility grid,
link in a communications network.

Other applications are found in the

layout of circuits,
network multicasting,
molecular biology, where Euler paths are used in the sequencing of DNA.

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

67 of 127

Necessary and Sufficient Conditions for Euler Circuits and Paths (continued)

Theorem: A connected multigraph with at least two vertices has an Euler circuit if and only if each of its vertices has an even degree and it has an Euler path if and only if it has exactly two vertices of odd degree.

Example: Two of the vertices in the multigraph model of the Kӧnigsberg bridge problem have odd degree. Hence, there is no Euler circuit in this multigraph and it is impossible to start at a given point, cross each bridge exactly once, and return to the starting point.

68 of 127

Understanding Mohammed’s Scimitars.

69 of 127

Eulerian Path is a path in a graph that visits every edge exactly once. Eulerian Circuit is an Eulerian Path that starts and ends on the same vertex.

Following is Fleury’s Algorithm for printing the Eulerian trail or cycle

Make sure the graph has either 0 or 2 odd vertices.
If there are 0 odd vertices, start anywhere. If there are 2 odd vertices, start at one of them.
Follow edges one at a time. If you have a choice between a bridge and a non-bridge, always choose the non-bridge.
Stop when you run out of edges.

The idea is, “don’t burn bridges“ so that we can come back to a vertex and traverse the remaining edges. For example, let us consider the following graph.

Fleury’s Algorithm for printing Eulerian Path or Circuit

70 of 127

Hamilton Paths and Circuits

William Rowan Hamilton

(1805- 1865)

Euler paths and circuits contained every edge only once.

Now we look at paths and circuits that contain every vertex exactly once.

William Hamilton invented the Icosian puzzle in 1857. It consisted of a wooden dodecahedron (with 12 regular pentagons as faces), illustrated in

(a), with a peg at each vertex, labeled with the names of different cities. String was used to used to plot a circuit visiting 20 cities exactly once. The graph form of the puzzle is given in (b).

The solution (a Hamilton circuit) is given here.

71 of 127

Hamilton Paths and Circuits

Definition: 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.

That is, a simple path x₀, x₁, …, x_n_-1, x_n in the graph G = (V, E) is called a Hamilton path if V = {x₀, x₁, … , x_n_-1, x_n } and x_i ≠ x_j for 0≤ i < j ≤ n, and the simple circuit x₀, x₁, …, x_n_-1, x_n, x₀(with n > 0) is a Hamilton circuit if x₀, x₁, … , x_n_-1, x_n is a Hamilton path.

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

72 of 127

Hamilton Paths and Circuits

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

73 of 127

Hamilton Paths and Circuits

Example: Which of these simple graphs has a Hamilton circuit or, if not, a Hamilton path?

Solution:

G₁does not have a Hamilton circuit (Why?), but does have a Hamilton path : a, b ,e , c, d.

G₂has a Hamilton circuit: a, b, c, d, e, a.

G₃has a Hamilton circuit: a,b,e,d,c,a

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

74 of 127

Necessary Conditions for�Hamilton Circuits

Unlike for an Euler circuit, no simple necessary and sufficient conditions are known for the existence of a Hamiton circuit.
However, there are some useful necessary conditions. We describe two of these now.

Dirac’s Theorem: If G is a simple graph with n ≥ 3 vertices such that the degree of every vertex in G is ≥ n/2, then G has a Hamilton circuit.

Ore’s Theorem: If G is a simple graph with n ≥ 3 vertices such that deg(u) + deg(v) ≥ n for every pair of nonadjacent vertices, then G has a Hamilton circuit.

Gabriel Andrew Dirac

(1925-1984)

Øysten Ore

(1899-1968)

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

75 of 127

Applications of Hamilton Paths and Circuits

Applications that ask for a path or a circuit that visits each intersection of a city, each place pipelines intersect in a utility grid, or each node in a communications network exactly once, can be solved by finding a Hamilton path in the appropriate graph.

The famous traveling salesperson problem (TSP) asks for the shortest route a traveling salesperson should take to visit a set of cities. This problem reduces to finding a Hamilton circuit such that the total sum of the weights of its edges is as small as possible.

A family of binary codes, known as Gray codes, which minimize the effect of transmission errors, correspond to Hamilton circuits in the n-cube Q_n.

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

76 of 127

ISOMORPHISM OF GRAPHS

Section 10.3

77 of 127

Isomorphism of Graphs

Definition: The simple graphs G₁ = (V₁, E₁) and G₂ = (V₂, E₂) are isomorphic if there is a one-to-one and onto function f from V₁ to V₂ with the property that a and b are adjacent in G₁ if and only if f(a) and f(b) are adjacent in G₂ , for all a and b in V₁ . Such a function f is called an isomorphism. Two simple graphs that are not isomorphic are called nonisomorphic.

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

78 of 127

Isomorphism of Graphs

It is difficult to determine whether two simple graphs are isomorphic using brute force because there are n! possible one-to-one correspondences between the vertex sets of two simple graphs with n vertices.

The best algorithms for determining weather two graphs are isomorphic have exponential worst case complexity in terms of the number of vertices of the graphs.

Sometimes it is not hard to show that two graphs are not isomorphic. We can do so by finding a property, preserved by isomorphism, that only one of the two graphs has. Such a property is called graph invariant.

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

79 of 127

Isomorphism of Graphs

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

Number of Vertices
Number of Edges
Degree of Sequence
Mapping

80 of 127

Isomorphism of Graphs (cont.)

Example: Show that the graphs G =(V, E) and H = (W, F) are isomorphic.

Solution: The function f with

f(u₁) = v₁,f(u₂) = v₄, f(u₃) = v₃, and f(u₄) = v₂ is a one-to-one

correspondence between V and W.

Note that adjacent vertices in G are

u₁ and u₂, u₁ and u₃, u₂ and u₄,

and u₃ and u₄. Each of the pairs

f(u₁) = v₁ and f(u₂) = v₄, f(u₁) = v₁

and f(u₃) = v₃ , f(u₂) = v₄ and

f(u₄) = v₂ , and f(u₃) = v₃ and

f(u₄) = v₂ consists of two adjacent vertices in H.

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

81 of 127

Example: Show that the graphs G =(V, E) and G’ = (W, F) are isomorphic.

Solution: The function f with

f(v1) = v1,f(v2) = v3, f(v3) = v5, f(v4) = v2 and f(v5) = v4 is a one-to-one correspondence between V and W.

Note that adjacent vertices in G are v1 and v2, v2 and v3, v3 and v4, v4 and v5 and v5 and v1.

Each of the pairs f(v1) = v1 and f(v2) = v3, f(v2) = v3 and f(v3) = v5 , f(v3) = v5 and

f(v4) = v2 , f(v4) = v2 and f(v5) = v4 and f(v5) = v4 and f(v1) = v1 consists of two adjacent vertices in H.

Isomorphism of Graphs

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

82 of 127

EXAMPLE: Determine whether the graph G and G’ given below are isomorphic.

SOLUTION:

As both the graphs have the same number of vertices. But the graph G has 7 edges and the graph G’ has only 6 edges. Therefore the two graphs are not isomorphic.

Note: As the edges of both the graphs G and G’ are not same then how the one-one correspondence is possible ,that the reason the graphs G and G’ are not isomorphic.

Isomorphism of Graphs

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

83 of 127

EXAMPLE: Determine whether the graph G and G’ given below are isomorphic.

SOLUTION:

Both the graphs have 5 vertices and 7 edges. The vertex q of G’ has degree 5. However G does not have any vertex of degree 5 (so one-one correspondence is not possible). Hence, the two graphs are not isomorphic.

Isomorphism of Graphs

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

84 of 127

EXAMPLE: Determine whether the graph G and G’ given below are isomorphic.

SOLUTION:

Clearly the vertices of both the graphs G and G’ have the same degree (i.e “2”) and having the same number of vertices and edges but isomorphism is not possible. As the graph G’ is a connected graph but the graph G is not connected due to have two components (eca and bdf). Therefore the two graphs are non isomorphic.

Isomorphism of Graphs

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

85 of 127

Isomorphism of Graphs

EXAMPLE: Determine whether the graph G and G’ given below are isomorphic.

SOLUTION:

Clearly G has six vertices, G’ also has six vertices. And the graph G has two simple circuits of length 3; one is abca and the other is defd. But G’ does not have any simple circuit of length 3(as one simple circuit in G’ is uxwvu of length 4).Therefore the two graphs are non-isomorphic.

Note: A simple circuit is a circuit that does not have any other repeated vertex except the first and last.

86 of 127

Isomorphism of Graphs

EXAMPLE: Determine whether the graph G and G’ given below are isomorphic.

SOLUTION:

Both the graph G and G’ have 8 vertices and 12 edges and both are also called regular graph(as each vertex has degree 3).The graph G has two simple circuits of length 5; abcfea(i.e starts and ends at a) and cdhgfc(i.e starts and ends at c). But G’ does not have any simple circuit of length 5 (it has simple circuit tyxut,vwxuv of length 4 etc). Therefore the two graphs are non-isomorphic.

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

87 of 127

Isomorphism of Graphs

EXAMPLE: Determine whether the given graph G and H are isomorphic.

Solution:

Solution: The function f with

f(a) = u, f(b) = v, f(c) = y, f(d) = x, f(e) = w and f(f) = z is a one-to-one correspondence between G and H.

Note that adjacent vertices in G are a and b, b and c, c and d, c and f, d and e, e and f and f and a.

Each of the pairs f(a) = u and f(b) = v, f(b) = v and f(c) = y , f(c) = y and f(d) = x , f(c) = y and f(f) = z , f(d) = x and f(e) = w, f(e) = w and f(f) = z and f(f) = z and f(a) = u consists of two adjacent vertices in H.

88 of 127

Algorithms for Graph Isomorphism

The best algorithms known for determining whether two graphs are isomorphic have exponential worst-case time complexity (in the number of vertices of the graphs).

However, there are algorithms with linear average-case time complexity.

You can use a public domain program called NAUTY to determine in less than a second whether two graphs with as many as 100 vertices are isomoprhic.

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

89 of 127

Applications of Graph Isomorphism

The question whether graphs are isomorphic plays an important role in applications of graph theory. For example,

chemists use molecular graphs to model chemical compounds. Vertices represent atoms and edges represent chemical bonds. When a new compound is synthesized, a database of molecular graphs is checked to determine whether the graph representing the new compound is isomorphic to the graph of a compound that this already known.
Electronic circuits are modeled as graphs in which the vertices represent components and the edges represent connections between them. Graph isomorphism is the basis for

the verification that a particular layout of a circuit corresponds to the design’s original schematics.
determining whether a chip from one vendor includes the intellectual property of another vendor.

90 of 127

10.6

Shortest-Path Problems

91 of 127

Weighted Graphs

Graphs that have a number assigned to each edge are called weighted graphs.

DEN

CHI

ATL

MIA

BOS

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

92 of 127

Weighted Graphs

DEN

CHI

ATL

MIA

BOS

MILES

2534

1855

957

834

349

2451

908

722

860

606

760

191

1090

595

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

93 of 127

Weighted Graphs

DEN

CHI

ATL

MIA

BOS

FARES

$129

$99

$79

$59

$89

$69

$129

$89

$39

$99

$79

$69

$39

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

94 of 127

Weighted Graphs

DEN

CHI

ATL

MIA

BOS

FLIGHT TIMES

4:05

2:55

2:20

2:10

3:50

2:00

1:15

2:10

1:40

1:30

1:55

2:45

0:50

1:50

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

95 of 127

Weighted Graphs

A weighted graph is a graph in which each edge (u, v) has a weight w(u, v). Each weight is a real number.

Weights can represent distance, cost, time, capacity, etc.

The length of a path in a weighted graph is the sum of the weights on the edges.

Dijkstra vs Bellman Ford vs Floyd Warshall

Dijkstra’s Algorithm finds the shortest path between two vertices.

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

96 of 127

Dijkstra’s Algorithm

Dijkstra’s algorithm is used in problems relating to finding the shortest path.

Each node is given a temporary label denoting the length of the shortest path from the start node so far.

This label is replaced if another shorter route is found.

Once it is certain that no other shorter paths can be found, the temporary label becomes a permanent label.

Eventually all the nodes have permanent labels.

At this point the shortest path is found by retracing the path backwards.

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

97 of 127

Dijkstra’s algorithm: example

Step

D(v)

D(w)

D(x)

D(y)

D(z)

∞

7,u

3,u

5,u

∞

11,w

6,w

5,u

14,x

11,w

6,w

uwx

uwxv

14,x

10,v

uwxvy

12,y

notes:

construct shortest path tree by tracing predecessor nodes
ties can exist (can be broken arbitrarily)

uwxvyz

98 of 127

Dijkstra’s algorithm: another example

Step

uxy

uxyv

uxyvw

uxyvwz

D(v)

2,u

D(w)

5,u

4,x

3,y

D(x)

1,u

D(y)

∞

2,x

D(z)

∞

4,y

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

99 of 127

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

100 of 127

Problem: shortest path from a to z

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

101 of 127

The Traveling Salesman Problem

The traveling salesman problem is one of the classical problems in computer science.
A traveling salesman wants to visit a number of cities and then return to his starting point. Of course he wants to save time and energy, so he wants to determine the shortest cycle for his trip.
We can represent the cities and the distances between them by a weighted, complete, undirected graph.
The problem then is to find the shortest cycle (of minimum total weight that visits each vertex exactly one).
Finding the shortest cycle is different than Dijkstra’s shortest path.� It is much harder too, no polynomial time algorithm exists!

102 of 127

The Traveling Salesman Problem

Importance:

Variety of scheduling application can be solved as a�traveling salesmen problem.
Examples:

Ordering drill position on a drill press.
School bus routing.

The problem has theoretical importance because it �represents a class of difficult problems known as NP-hard problems.

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

103 of 127

Travelling Salesman problem

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

104 of 127

Travelling Salesman problem

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

105 of 127

10.7 �Planar Graphs

106 of 127

The House-and-Utilities Problem

107 of 127

Planar Graphs

A graph is called planar if it can be drawn in the plane without any edges crossing.
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.

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

108 of 127

Example

A graph may be planar even if it is usually drawn with crossings, since it may be possible to draw it in another way without crossings.

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

109 of 127

Example

A graph may be planar even if it represents a 3-dimensional object.

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

110 of 127

Planar Graphs

We can prove that a particular graph is planar by showing how it can be drawn without any crossings.
However, not all graphs are planar.
It may be difficult to show that a graph is nonplanar. We would have to show that there is no way to draw the graph without any edges crossing.

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

111 of 127

Regions

Euler devised a formula for expressing the relationship between the number of vertices, edges, and regions of a planar graph.
These may help us determine if a graph can be planar or not.

112 of 127

Euler’s Formula

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.

# of edges, e = 6

# of vertices, v = 4

# of regions, r = e - v + 2 = 4

R₄ R₃ R₂

R₁

113 of 127

Euler’s Formula (Cont.)

Corollary 1: If G is a connected planar simple graph with e edges and v vertices where v ≥ 3, then e ≤ 3v - 6.
Is K₅planar?

K₅

114 of 127

Euler’s Formula (Cont.)

K₅ has 5 vertices and 10 edges.
We see that v ≥ 3.
So, if K₅ is planar, it must be true that e ≤ 3v – 6.
3v – 6 = 3*5 – 6 = 15 – 6 = 9.
So e must be ≤ 9.
But e = 10.
So, K₅is nonplanar.

K₅

115 of 127

Euler’s Formula (Cont.)

Corollary 2: If G is a connected planar simple graph, then G must have a vertex of degree not exceeding 5.

If G has one or two vertices, it is true;

thus, we assume that G has at least three vertices.

If the degree of each vertex were at least 6, then by Handshaking Theorem,

2e ≥ 6v, i.e., e ≥ 3v,

but this contradicts the inequality from

Corollary 1: 1 e ≤ 3v – 6.

116 of 127

Euler’s Formula (Cont.)

Corollary 3: If a connected planar simple graph has e edges and v vertices with v ≥ 3 and no circuits of length 3, then e ≤ 2v - 4.
Is K_3,3planar?

117 of 127

Euler’s Formula (Cont.)

K_3,3 has 6 vertices and 9 edges.
Obviously, v ≥ 3 and there are no circuits of length 3.
If K_3,3 were planar, then e ≤ 2v – 4 would have to be true.
2v – 4 = 2*6 – 4 = 8
So e must be ≤ 8.
But e = 9.
So K_3,3is nonplanar.

K_3,3

118 of 127

Kuratowski’s Theorem

We have seen that K3,3 and K5 are not planar. Clearly, a graph is not planar if it contains either of these two graphs as a subgraph. Surprisingly, all nonplanar graphs must contain a subgraph that can be obtained from K3,3 or K5 using certain permitted operations. If a graph is planar, so will be any graph obtained by removing an edge {u, v} and adding a new vertex w together with edges {u,w} and {w, v}. Such an operation is called an elementary subdivision. The graphs G1 = (V1, E1) and G2 = (V2, E2) are called homeomorphic if they can be obtained from the same graph by a sequence of elementary subdivisions

119 of 127

10.8 Graph Coloring

120 of 127

10.8 Graph Coloring

121 of 127

10.8 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.)

THEOREM 1

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

122 of 127

10.8 Graph Coloring

123 of 127

10.8 Graph Coloring

124 of 127

10.8 Graph Coloring

125 of 127

Applications of Graph Colorings

Scheduling Final Exams How can the final exams at a university be scheduled so that no student has two exams at the same time?

Solution: 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 final 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 finals 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. A coloring of the graph using four colors and the associated schedule are shown in Figure 9.