EECS 203: Discrete Mathematics

Winter 2019
Discussion 10 - Notes

1 Definitions
• Graph:

• Simple Graph:

• Multigraph:

• Loop:

• Directed Graph:

• Adjacent Vertices:

• Neighborhood:

• Complete Graph, Kn :

• Cycle, Cn :

• Wheel, Wn :

• Hypercube, Qn :

• Degree of a vertex:

• The Handshaking Theorem:

• Bipartite:

Solution:

1
• Equivalence Relations: A relation on a set A is called an equivalence
relation if it is reflexive, symmetric, and transitive.

• Equivalence Class: An equivalent class of an element a with the respect

to R, is a set of all elements from a set A that is related to a. i.e., [a]R =
{x|x ∈ A ∧ xRa}.

• Partition: a partition of a set S is a collection of disjoint nonempty subsets

of S that have S as their union. Moreover, the equivalent classes of any
equivalent relation always form a partition.

• Partial order: A relation R on a set S is called a partial ordering or partial

order if it is reflexive, antisymmetric, and transitive. A set S together with
a partial ordering R is called a partially ordered set, or poset.

• Total order: If (S, ) is a poset and every two elements of S are comparable,
S is called a totally ordered or linearly ordered set. We can think of total
ordering like a chain of elements.

• Graph: A graph G = (V, E) consists of V , a set of vertices, and E, a set

of edges. Each edge has either one or two vertices associated with it, where
there is only one if the edge is a loop.

• Simple Graph: A graph in which each edge connects two different vertices
and where no two edges connect the same pair of vertices.

• Multigraph: Graphs that may have multiple edges connecting the same
vertices.

• Loop: An edge that connects a vertex to itself.

• Directed Graph: A graph where each edge is associated with an ordered

pair of vertices, (u, v), and the edge is said to start at u and end at v.

• Adjacent Vertices: Two vertices are adjacent if there is an edge that

connects them. This edge is said to connect the two vertices.

• Neighborhood: A neighborhood of a vertex, v, is the set of all adjacent

(or neighbor) vertices of that vertex and is denoted as N (v). For a set of
vertices, A, the neighborhood of A, denoted N (A), is the set of all neighbor
vertices to any vertex within the set A.

• Complete Graph: a simple graph that contains exactly one edge between
each pair of distinct vertices

2
 • Cycle, Cn : a simple graph that consists of n vertices v1 , v2 , ..., vn and edges
{v1 , v2 }, {v2 , v3 }, ..., {vn−1 , vn }, and {vn , v1 }.

• Wheel, Wn : a simple graph constructed from a cycle Cn by adding an

additional vertex (usually in the middle) and connecting the new vertex to
each of the vertices from Cn .

• Hypercube, Qn : a graph that has vertices representing the 2n bit strings

of length n. Two vertices are adjacent if and only if the bit strings that they
represent differ in exactly one bit position.

• Degree of a vertex: The degree of a vertex is equal to the number of

edges incident with it, except that a loop at a vertex contributes twice to
the degree of that vertex. The degree of the vertex v is denoted by deg(v).

• The Handshaking Theorem: Let G = (V, E) be an undirected graph

with m edges. Then:
X
2m = deg(v)
v∈V

• Bipartite: A simple graph G is called bipartite if its vertex set V can be

partitioned into two disjoint set V1 and V2 such that every edge in the graph
connects a vertex in V1 and a vertex in V2 . The pair (V1 , V2 ) is called a
bipartition of the vertex set V .

1. Section 9.5 Problem 15

Let R be the relation on the set of ordered pairs of positive integers such that
((a, b), (c, d)) ∈ R iff a + d = b + c. Show that R is an equivalence relation.

Solution:
• Reflexivity: Clearly, a + b = b + a since addition is commutative.

• Symmetry: If a + d = b + c, then c + b = b + c = a + d = d + a since addition

is commutative, and thus ((c, d), (a, b)) ∈ R

• Transitivity: Suppose (a, b)R(x, y) and (x, y)R(e, f ). Then

a+f = a+y−y+f = b+x−y+f = x+f +b−y = y+e+b−y = b+e

since addition is associative and commutative, and thus (a, b)R(e, f ).

3
2. Section 9.5 Problem 58
Each bead on a bracelet with three beads is either red, white, or blue, as illustrated in
the figure shown. Define the relation R between bracelets as: (B1 , B2 ), where B1 and
B2 are bracelets, belongs to R if and only if B2 can be obtained from B1 by rotating
it or rotating it and then reflecting it.

(a) Show that R is an equivalence relation.

(b) What are the equivalence classes of R?

Solution:

(a) We show the three properties of R.

1. First, it is reflexive since a bracelet is itself rotated by 0 (or 360, 720...)

2. It is also transitive since the composite of two rotations is a rotation;
composite of a rotation and a rotation-reflection is a rotation-reflection; a
rotation-reflection composed with rotation is just the same as the previous
one, swapping the order; and finally, a composite of two rotation-reflection
is just a rotation, as reflection is keeping one bead in-place, and swapping
the other two.
3. Finally, it is symmetric because all of the action are reversible, since we
can rotate 360-previous angle, and reflect with the respect to the same axis
if needed.

(b) The equivalence classes are the indistinguishable bracelets. If we denote a

bracelet by the colors of its beads, then these classes can be described as
RRR, WWW, BBB, RRW, RRB, WWR, WWB, BBR, BBW, and RWB.

3. Modified Section 9 Review Problem 21

How many different equivalence relations with exactly five different equivalence classes
are there on a set with seven elements?

Solution: This is a combinatorial question with an equivalence relation twist.

The question essentially asks: How many ways are there to put 7 labeled balls
into 5 unlabeled boxes? Note that the balls must be distinct, because we have
a set of 7 elts. This was a problem done in homework 7 Q5, and the answer is
reproduced below:

4
 If the number of balls in the boxes are 1,1,1,1,3, we only need to pick the three
balls that are in the same box. There are C(7, 3) = 35 ways. (2) If the number of
balls in the boxes are 1,1,1,2,2, we need to pick the two groups of two balls. there
are C(7, 2) × C(5, 2)/2 = 105 ways. In total, there are 140 ways.

4. Section 9.6 Problem 34

Answer these questions for the poset ({2, 4, 6, 9, 12, 18, 27, 36, 48, 60, 72}, |).
a) Find the maximal elements.
b) Find the minimal elements.
c) Is there a greatest element?
d) Is there a least element?
e) Find all upper bounds of {2, 9}.
f) Find the least upper bound of {2, 9}, if it exists.
g) Find all lower bounds of {60, 72}.
h) Find the greatest lower bound of {60, 72}, if it exists.

Solution:
60 48 72 27

36

12 18

4 6

2 9

5
 a) 27, 48, 60, and 72. These numbers are maximal, since each divides no number
in the list other than itself. All the other numbers divide 72, so they are not
maximal.

b) 2 and 9 These numbers are minimal, since each is divisible by no other number
in the list other than itself. Every other element is divisible by either 2 or 9.

c) None. There is no greatest element, since there is no number in the set which
is divisible by both 60 and 72.

d) None. There is no least element, since there is no number in the set that
divides both 2 and 9.

e) 18, 36, and 72. These numbers are the upper bounds, since they are divisible
by both 2 and 9. No other numbers in the list are divisible by both 2 and 9.

f) 18. This is the least upper bound, since it is the upper bound which divides
all other upper bounds.

g) 2, 4, 6, and 12. These elements are the lower bounds, since they divide both
60 and 72. No other numbers in the list divide both 60 and 72.

h) 12. This is the greatest lower bound, since it is the lower bound which is
divisible by all the other lower bounds.

5. Section 9.6 Problem 36

Give a poset that has

(a) a minimal element but no maximal element

(b) a maximal element but no minimal element

(c) neither a maximal nor a minimal element

Solution:

(a) One example is the natural numbers under “is less than or equal to.” Here 1
is the (only) minimal element, and there are no maximal elements.

(b) Dual to part (a), the answer is the natural numbers under “is greater than or
equal to.”

6
 (c) Combining the answers for the first two parts, we look at the set of integers
under “is less than or equal to.” Clearly there are no maximal or minimal
elements.

6. Section 10.1 Exercise 2

What kind of graph (from Table 1) can be used to model a highway system between
major cities where:

a) there is an edge between the vertices representing cities if there is an interstate

highway between them?

Solution: A simple graph would be the model here, since there are no parallel
edges or loops, and the edges are undirected.

b) there is an edge between the vertices representing cities for each interstate highway
between them?

Solution: A multigraph would, in theory, be needed here, since there may be

more than one interstate highway between the same pair of cities.

c) there is an edge between the vertices representing cities for each interstate highway
between them, and there is a loop at the vertex representing a city if there is an
interstate highway that circles this city?

Solution: Same as part (b), but including self-loops for cities with circling
highways. This is also known as a pseudograph.

7. Section 10.1 Exercise 22

Construct the call graph for a set of seven telephone numbers 555-0011, 555-1221,
555-1333, 555-8888, 555-2222, 555-0091, and 555-1200 if there were three calls from
555-0011 to 555-8888 and two calls from 555-8888 to 555-0011, two calls from 555-
2222 to 555-0091, two calls from 555-1221 to each of the other numbers, and one call
from 555-1333 to each of 555-0011, 555-1221, and 555-1200.

7
 Solution:
This is a directed multigraph with one edge from a to b for each call made by
a to b. Rather than draw the parallel edges with parallel lines, we have indicated
what is intended by writing a numeral on the edge to indicate how many calls
were made, if it was more than one.

1333 0011

1200 1221 8888

2222 0091

8. Exercise 10.1.28
Describe a graph that represents a subway system in a large city. Should edges be
directed or undirected? Should multiple edges be allowed? Should loops be allowed?

Solution:
We make the subway stations the vertices, with an edge from station u to station
v if there is a train going from u to v without stopping. This is quite possible
that some segments are one-way, so we should use directed edges. Multiple edges
would be allowed if there are two different types of trains from one station to
another, such as a local and express train. In that case, there could be parallel
edges between the same vertices, because both a local and express train might
travel the same segment. There would be no point in having loops, because no
passenger would want to travel from a station back to the same station without
stopping.

9. Problem 10.2 Exercise 26

For which values of n are these graphs bipartite?

a) Kn

b) Cn

8
c) Wn
d) Qn

Solution:

a) K1 does not have enough vertices to be bipartite. Clearly K2 is bipartite. There

is a triangle in Kn for n > 2, so they are not bipartite.

b) Cn is defined for n > 3. If n is even, then Cn is bipartite, since we can take

one part to be every other vertex. If n is odd, then Cn is not bipartite.

c) Every wheel contains triangles, so no Wn is bipartite.

d) Qn is bipartite for all n ≥ 1, since we can divide the vertices into these two
classes: those bit strings with an odd number of 1’s, and those bit strings with
an even number of 1’s.

10. Section 10.2 Not in Book 4

Give an example of a real-life situation that could be modeled using the following
graphs. Clearly indicate what the vertices and edges represent in each situation.
(a) W6
(b) C5
(c) Kn

Solution: Answers will vary. The following are examples.

(a) A wheel of size 6 could be used to describe 6 different control stations that
each communicate with their neighboring control station and a central control
station only. Each vertex represents a control station and each edge represents
a path for communication.

(b) A cycle of size 5 could represent a road trip. Each of the 5 vertices represents
a certain destination to visit and each edge represents the traveling path from
one destination to another, starting and ending at the same location.

(c) A complete graph of size n could represent a group of n close friends who
are all individually friends with every other person in the group. Each vertex
represents a person in the group and each edge represents a friendship.

9
11. 10.2.52
Let G be a graph with v vertices and e edges. Let M be the maximum degree of the
vertices of G, and let m be the minimum degree of the vertices of G. Show that

a) 2e/v ≥ m

b) 2e/v ≤ M

Solution:
P
a.) From Theorem 1, we know that 2e = v∈V deg(v). Each vertex is of degree
no less than m, so the minimum the sum of the degrees of the vertices can be
is vm. Thus, we know that 2e ≥ vm. Thus, 2e/v ≥ m. (This is the application
of purified pigeonhole principle)
P
b.) From Theorem 1, we know that 2e = v∈V deg(v). Each vertex is of degree
no greater than M , so the maximum the sum of the degrees of the vertices
can be is vM . Thus, we know that 2e ≤ vM . Thus, 2e/v ≤ M . (This is the
application of purified pigeonhole principle)

10