LESSON 1: GRAPHS AND EULER CIRCUITS Example 1: Constructing a Graph.

The following
table lists five students at a college. An “X”
Think of all various connections we experience
indicates that the two students participate in
in our lives – friends are connected on
the same study group this semester.
Facebook, cities are connected by roads,
computers are connected across Internet. A
branch of Mathematics called graph theory
illustrates and analyzes connections such as
these.

For example, the diagram in Figure 1 could

represent friends that are connected on
Facebook. Each dot represents a person, and a
line segment connecting two dots means that a) Draw a graph that represents this
those two people are friends on Facebook. This information where each vertex represents a
type of diagram is called a graph. student and an edge connects two vertices if
the corresponding students study together.

b) Use your graph to answer the following

questions: Which student is involved in the
most study groups with the others? Which
student has only one study group in common
with the others? How many study groups does
Laura have in common with the others?

Solution
 A graph is a set of points called vertices
and line segments or curves called a.) We draw five vertices (in any configuration
edges that connect vertices we wish) to represent the five students, and
connect the vertices with edges according to
The three graphs in Figure 2 are the same graph
the table.
as in Figure 1 but used in different contexts.
Note that the replacement of the vertices has b.) The student which involved in the most
nothing to do with geographical location; in study groups with the others is Amber. The
fact, the vertices can be shown in any student which has only one study group in
arrangement we choose. common with the others is Kayla. Laura has two
study groups in common with the others.

The graph in Figure 4a has five vertices but no

edges and is referred to a null graph. It is also
an example of a disconnected graph.

The Figure 4b is a connected graph that has a

pair of multiple edges.
Note that two edges cross in the center, but
there is no vertex there. Unless a dot is drawn,
EULER CIRCUITS
the edges are considered to pass over each
other without touching. In the early eighteenth century, the Pregel River
in a city called Konigsberg (located in modern-
day Russia and now called Kaliningrad)
surrounded an island before splitting in two.
Seven bridges crossed the river and connected
four different land areas, similar to the map
drawn below (Figure 7)

The graph in Figure 4c is not connected: it

consists of two different sections. It also
contains a loop.

Figure 4d is a connected graph in which every

possible edge is drawn between vertices
(without any multiple edges). Such a graph is
called a complete graph.

A path in a graph can be thought of as a

movement from one vertex to another by
traversing edges. We can refer to our
movement by vertex letters. For example, in the
graph in Figure 8b, one path would be A–B–A–
C. If a path ends at the same vertex, at which it
started, it is considered a closed path, or circuit.
The three graphs shown below are considered For the graph in Figure 9, the path A–D– F–G–E–
equivalent graphs because the edges form the B–A is a circuit because it begins and ends at
same connections of vertices in each graph. the same vertex. The path A–D–F–G–E–H is not
a circuit, as it does not begin and end at the
same vertex
 EULER CIRCUIT - A circuit that uses EULER PATHS
every edge, but never uses the same
 Euler Path Theorem: A connected graph
edge twice. (The path may cross
contains an Euler path if and only if the
through vertices more than once). The
graph has two vertices of odd degree
path B–D–F–G– H–E–C–B–A–D–G–E–B
with all other vertices of even degree.
in Figure 9 is an Euler circuit. It begins
 Every Euler path must start at one of
and ends at the same vertex and uses
the vertices of odd degree and end at
every edge exactly once. The path A–B–
the other.
C–E–H–G–E–B–D–A is not an Euler
circuit. A photographer would like to travel across all of
 The path begins and ends at the same the roads shown on the following map. The
vertex but it does not use edges DF, DG, photographer will rent a car that need not be
or FG. The path A–B–C–E–H–G–F–D–A– returned to the same city, so the trip can begin
B–E–G–D–A begins and ends at A but in any city. Is it possible for the photographer to
uses edges AB and AD twice so it is not design a trip that traverses all of the roads
an Euler circuit. exactly once?
 For an Euler circuit to exist, the degree
of every vertex would have to be an
even number. Furthermore, he was
able to show that any graph that has
even degree at every vertex must have
an Euler circuit. Consequently, such
graphs are called Eulerian.

Theorem 1: Eulerian Graph Theorem: A

connected graph is Eulerian if and only if every
vertex of the graph is of even degree.

Figure 10a does have an Euler circuit (C and D

are of odd degree), Figure 10b has an Euler
circuit (All vertices are of even degree).

Solution:

Let be the first letter of the word represents the

city (Alameda = A, Burley = B, Caldwell = C,
Dover = D, Evanston = E, Fairmont = F,
Grangeville = G). Determine if the Figure 12a
contains an Euler Path. Since each vertex
The graph (Figure 11) shown does not have an
(represents as city) has an even degree and two
Euler circuit (B, C, E, G are not of even degree)
vertices have an odd degree, then the graph
contains an Euler Path. The possible trip of the Using Dirac’s Theorem, the graph is Hamiltonian
photographer is A-B-C-D-B-F-A-G-F-E-D. because it contains at least three vertices, each
vertex does not contain multiples edges and
every vertex has degree of at least
HAMILTONIAN CIRCUITS AND WEIGHTED One Hamiltonian circuit is Portland-Boise-Butte-
GRAPHS Salt Lake City-Reno-Sacramento-Portland, which
For instance, Figure 12 shows the map of represents a sequence of flights that visits each
cities. If our priority is to visit each city, we city and returns to the starting city without
could travel along the route A–B–C–D–E–F– visiting any city twice.
G–A (abbreviating the cities). This path
visits each vertex once and returns to the  WEIGHTED GRAPH is a graph in which
starting vertex without visiting any vertex each edge is associated with a value,
twice. We call such a path a Hamiltonian called weight.
circuit.
 Hamiltonian Circuit. A Hamiltonian
circuit is a path that uses each The table below lists the distances in miles
vertex of a graph exactly once. A between six popular cities that a particular
graph that contains a Hamiltonian airline fly to. Suppose a traveler would like to
start in Chicago, visit the other five cities this
circuit is called Hamiltonian.
airline flies to, and return to Chicago. Find three
Theorem 3: different routes that the traveler could follow,
and find the total distance flown for each route.
DIRAC’S THEOREM. Consider a connected graph
with at least three vertices and no multiple
edges. Let 𝑛 be the number of vertices in the
graph. If every vertex has degree of at least
𝑛/2 , then the graph must be Hamiltonian.

The graph below shows the available flights of a

popular airline. (An edge between two vertices
in the graph means that the airline has direct
flights between the two corresponding cities.) Solution:
Apply Dirac’s theorem to verify that the
following graph is Hamiltonian. Then find a The various solution will be simpler to analyze if
Hamiltonian circuit. What does the Hamiltonian we first organize the information in a graph.
circuit represent in terms of flights? Begin by letting each city be represented by a
vertex. Draw an edge between two vertices if
there is a flight between the corresponding
cities, and label each edge with a weight that
represents the number of miles between the
two cities. A route that visits each city just once
corresponds to a Hamiltonian circuit. Beginning
at Chicago, one such circuit is Chicago-New
York-Dallas-Philadelphia-Atlanta-Washington
DC-Chicago. By adding the weights of each edge
in the circuit, we see that the total number of
Solution:
miles travelled is 713 + 1374 + 1299 + 670 + 544 2. After arriving at the next vertex, travel along
+ 597 = 5197. the edge of smallest weight that connects to a
vertex not yet visited. Continue this process
until you have visited all vertices.

3. Return to the starting vertex.

Use the greedy algorithm to find a Hamiltonian

circuit in the weighted graph shown in Figure
16. Start at vertex A

ALGORITHMS IN COMPLETE GRAPHS

The graph shown in Figure 15, with only 6 Solution:
vertices, has 60 unique Hamiltonian circuits. If
 Begin at A. The weights of the edges
we have a graph with 12 vertices, and every
from A are 13, 5, 4, 15, and 8. The
vertex is connected to every other by an edge,
there are almost 20 million different smallest is 4.
Hamiltonian circuits! There are two algorithms,  Connect A to D. At D, the edge with the
the greed algorithm and the edge-picking smallest weight is DB.
algorithm, that can be used to find a solution.  Connect D to B. At B, the edge with the
Both of these algorithms apply only to complete smallest weight is BF. Connect B to F. At
graphs – graphs in which every possible edge is F, the edge with the smallest weight, 7,
drawn between vertices (without any multiple is FD.
edges). For instance, the graph in is a complete  However, D has already been visited.
graph with six vertices. Choose the next smallest weight, edge
FE. Connect F to E.
 At E, the edge with the smallest weight
whose vertex has not been visited is C.
 Connect E to C. All vertices have been
visited, so we are at step 3 of the
algorithm.
 We return to the starting vertex by
connecting C to A. The Hamiltonian
circuit is A-D-B-F-E-C-A. The weight of
the circuit is 4+2+5+10+6+15=42.
THE GREEDY ALGORITHM

1. Choose a vertex to start at, then travel along THE EDGE-PICKING ALGORITHM
the connected edge that has the smallest
weight. (If two or more edges have the same 1. Mark the edge of smallest weight in the
weight, pick any one.) graph. (If two or more edges have the same
weight, pick any one.)
2. Mark the edge of next smallest weight in the F-B-D-A.) The total weight of the circuit
graph, as long as it does not complete a circuit is 4+2+5+14+6+5=36.
and does not add a third marked edge to a

single vertex.

3. Continue this process until you can no longer

mark any edges. Then mark the final edge that
PLANAR GRAPH
completes the Hamiltonian circuit.
 A planar graph is a graph that can be
drawn so that no edges intersect each
Use the edge-picking algorithm to find a other (except at vertices). If the graph is
Hamiltonian circuit in Figure 17. drawn in such a way that no edges
cross, we say that we have a planar
drawing of the graph.

Show that the following graph below is planar.

Solution: Solution:

 We first highlight the edge of smallest

weight, namely BD with weight 2. The
edge of next smallest weight is AD with
weight 4.
 The next smallest weight is 5, which
appears twice, with edges AE and FB.
 We can mark both of them. There are
two edges of weight 6 (the next
smallest weight), BC and EC. We cannot
use BC because it would add a third
marked edge to vertex B.
 We mark edge EC. We are now at step 3
of the algorithm; any edge we mark will Solution: First redraw the highlighted edge as
either complete a circuit or add a third shown.
edge to a vertex. So, we mark the final
edge to complete the Hamiltonian
circuit, edge FC.
 Beginning at vertex A, the Hamiltonian
circuit is A-D-B-F-C-E-A. (In the reverse
direction, an equivalent circuit is A-E-C-
Now redraw the two vertices and the edges that
meet there, as shown below
b.

The result is a graph with no intersecting edges.

Solution: The highlighted edges in the graph,
Therefore, the graph is planar.
considered as a subgraph, form the graph K5.

SUBGRAPH THEOREM

 If a graph G has a subgraph that is not

planar. In particular, if G contains the We can expand this strategy by considering
Utilities Graph or 𝐾5, as a subgraph, G contractions of a subgraph.
is not planar.  Contraction of a graph is formed by
“shrinking” an edge until the two
Show that the following graph is not planar: vertices it connects come together
a. and blend into one. If, in the
process, the graph is left with any
multiple edges, we merge them into
one. The process is illustrated below

Solution: In the figure below, we have

highlighted edges connecting the top six
vertices. If we consider the highlighted edges
and attached vertices as a subgraph, we can
verify that the subgraph is the Utilities Graph NONPLANAR GRAPH THEOREM
 A graph is nonplanar if and only if
has the Utilities Graph or 𝐾5 as a
subgraph, or it has a subgraph that
can be contracted to the Utilities
Graph or 𝐾5

a.
Solution: a) Note that the graph looks similar to
K5. In fact, we can contract some edges and
make the graph look like K5. Choose a pair of
adjacent outside edges and contract one of
them.

EULER’S FORMULA

 Euler noticed a connection between

various features of planar graphs. In
addition to edges and vertices, he
looked at faces of a graph. In a planar
drawing of graph, the edges divide the
graph into different regions called faces.
The region surrounding the graph, or
the exterior, is also considered a face,
called infinite face. The following
relationship is always true.
 Euler’s Formula. In a connected planar
graph drawn with no intersecting edges,
let v be the number of vertices, e the
number of edges, and f the number of
faces. Then, 𝑣 + 𝑓 = 𝑒 + 2.
b.

FOUR-COLOR THEOREM.

 Every planar graph is 4-colorable.

THE CHROMATIC NUMBER OF GRAPH

 The four-color theorem guarantees that

Solution: b) The graph looks similar to the we need only four colors to color a
Utilities Graph. Contract edges as shown below, planar graph; however, if we wish to
and combine the resulting multiple edges. If we color a nonplanar graph, we may need
do the same on the right side of the graph, we more than four colors.
are left with the Utilities Graph.  The minimum number of colors needed
to color a graph so that no edge
connects vertices of the same color is
called the chromatic number of the
graph.

THEOREM 7: 2-COLORABLE GRAPH THEOREM.

 A graph is 2-colorable if and only if it  We can represent the traffic patterns
has no circuits that consist of an odd with a graph; each vertex will represent
number of vertices. one of the six possible traffic paths, and
we will draw an edge between two
vertices if the corresponding paths
would allow vehicles to collide.
 The result is the graph shown in Figure
10 because we do not want to allow
vehicles to travel simultaneously along
routes on which they could collide, any
vertices connected by an edge can allow
Find the chromatic number of Utilities Graph.
traffic to move only during different
parts of the light cycle.
 We can represent each portion of the
cycle by a color. Our job then is to color
the graph using the fewest possible
colors.

Solution:

 Note the graph contains circuits such as

A-Y-C-Z-B-X-A with six vertices and A-Y-
B-X-A with four vertices.
 It seems that any circuit we find, in
fact, involves an even number of
vertices. It is difficult to determine
whether we have looked at all possible
circuits, but our observations suggest There is no 2-coloring of the graph because we
that the graph may be 2-colorable. have a circuit of length A–D–E–A. We can,
 A little trial and error confirms this if however, find a 3-coloring. One possibility is
we simply color vertices A, B, and C one given in Figure 11.
color and the remaining vertices
another.

MODELING TRAFFIC LIGHTS WITH GRAPHS

 We can design a traffic-light cycle by

modeling an intersection with a graph.
Figure 9 shows a three-way intersection
where two two-way roads meet.
 Each direction of traffic has turn lanes,
with left-turn lights where possible.
There are six different directions in  A 3-COLORING OF THE GRAPH means
which vehicles can travel, as indicated that the traffic lights at the intersection
in the figure, and we have labeled each will have to go through a three-stage
possibility with a letter. cycle. One stage will allow the traffic
routes corresponding to the red vertices area. An edge connects two vertices if the
to proceed, the next stage will let the corresponding freeways have interchanges
paths corresponding to the blue allowing drivers to transfer from one
vertices to proceed, and finally, the freeway to the other. Which freeways have
third stage will let path E, colored interchanges to all the other freeways in the
green, proceed. graph?

 405

What is an Euler circuit of the graph A school bus driver would like to bring the
below? kids back to their homes along a least
expensive route. This example deals about?

 Hamiltonian

If a planar drawing of a graph has 100

vertices and 50 faces, how many edges are
in the graph?

 148

 A-B-A-D-C-D-E-F-E-B-C-

Using the greedy algorithm, what is the Which graph is Eulerian?

Hamiltonian circuit beginning at vertex A in
the weighted graph shown below?

If a planar drawing of a graph has 15 edges

and 8 vertices, how many faces does the
graph have?

 9
 A-E-D-B-C-F-A

What is the Euler path of the given graph

below?
Each vertex in the graph at the left
represents a freeway in the Los Angeles
 B-C-F-D-E-A-B-D-A-C-E

A garbage collector would like to collect the

garbage in all the streets of a subdivision
along a shortest possible path. This
example deals about?

 Eulerian

Which graph is planar?

Which graph is NOT Hamiltonian?