Discrete Mathematics and Graph Theory Assignment
Assignment Questions
1. Prove that if R is a transitive relation on a set A, then Rn ⊆ R for all positive integers n, where Rn denotes
the n-fold composition of R with itself.
2. Let A be a set with n elements. Find the number of strict partial orders on A (irreflexive, antisymmetric,
and transitive relations). Compute this for n = 3.
3. Let A = {1, 2, 3, . . . , 10} and B = {1, 2, 3, 4, 5}. How many functions f : A → B satisfy the condition that
f −1 (1) ∪ f −1 (2) = {1, 2, 3, 4, 5, 6}?
4. Consider the relation R on R2 defined by (a, b)R(c, d) iff a + d = b + c. Prove that R is an equivalence relation
and describe geometrically what each equivalence class represents.
5. Consider the poset (D30 , |) where D30 is the set of all positive divisors of 30. Find the number of maximal
chains from 1 to 30 in this poset.
6. Let A = {a, b, c, d} and B = {1, 2, 3}. Determine whether the relation R from A to B is a function. If it is a
function, give its range.
(a) R = {(a, 3), (b, 2), (c, 1)}
(b) R = {(a, 1), (b, 1), (c, 1), (d, 1)}
7. Let A = R and f : A → R be defined by f (a) = a2 . Prove or disprove that f (a1 + a2 ) = f (a1 ) + f (a2 ).
8. How many students must be in a class to guarantee that at least two students receive the same score on the
final exam, if the exam is graded on a scale from 0 to 100 points, if the points have integer increments and if
half points (0.5 points) are valid too?
9. Suppose that a computer science laboratory has 15 workstations and 10 servers. A cable can be used to
directly connect a workstation to a server. For each server, only one direct connection to that server can
be active at any time. We want to guarantee that at any time, any set of 10 or fewer workstations can
simultaneously access different servers via direct connections. Although we could do this by connecting
every workstation directly to every server (using 150 connections), what is the minimum number of direct
connections needed to achieve this goal?
10. Let A = {1, 2, 3, 4, 12}. Consider the partial order of divisibility on A. That is, if a, b ∈ A, then a ≤ b if and
only if a | b. Draw the Hasse diagram of the poset (A, ≤).
11. A drawer contains a dozen brown socks and a dozen black socks, all unmatched. A man takes socks out at
random in the dark.
(a) How many socks must he take out to be sure that he has at least two socks of the same colour?
(b) How many socks must he take out to be sure that he has at least two black socks?
12. Reconsider 1, 2, 3, 4, 6, 8, 12, 24 under lcm and gcd. Identify its algebraic structure.
13. For non-empty finite sets A, B, consider existence of bijections from A to B and from A × A to A ∪ B. What
constraints must hold between |A| and |B|?
14. Which one of the following is NOT necessarily a property of a group?
(a) Associativity: (ab)c = a(bc) for all a, b, c ∈ G.
(b) Existence of identity e ∈ G with ae = ea = a for all a ∈ G.
1
(c) Existence of inverses: for every a ∈ G there exists a−1 ∈ G with aa−1 = a−1 a = e.
(d) Commutativity: ab = ba for all a, b ∈ G.
15. Let S be a semigroup such that for all a, b, c ∈ S certain relations hold (e.g. (xy)2 = x2 y 2 ). Decide whether
S must be commutative.
16. Consider the set 1, 2, 3, 4, 6, 8, 12, 24 with two binary operations: lcm and gcd. Which structure does this
set represent: group, ring, field, or lattice? Explain.
17. Let S = {0, 1, 2, . . . , 7} with operation ⊗ defined as multiplication modulo 8.
(a) Prove that (S, ⊗) is not a group.
(b) Identify three distinct 2-element subsets G ⊂ S that are groups under ⊗.
18. For the set {1, ω, ω 2 }, where ω is a primitive cube root of unity, under multiplication ∗, what algebraic
structure does ({1, ω, ω 2 }, ∗) form?
19. If a binary operation ⊕ on integers is defined by x ⊕ y = x2 + y 2 , which of the following properties hold:
associativity, commutativity, identity, inverses?
20. Let S = {0, 1, 2, . . . , 7} with operation ⊗ defined as multiplication modulo 8.
(a) Prove that (S, ⊗) is not a group.
(b) Identify three distinct 2-element subsets G ⊂ S that are groups under ⊗.
21. Given the degree sequence: 7, 7, 6, 5, 5, 4, 3, 3, 2, 2
Use the Havel–Hakimi algorithm to determine whether a simple graph exists with this degree sequence.
22. Given graph:
Edges: (1,4), (2,4), (2,5), (3,5), (3,6), (1,6)
(a) Check whether the graph is bipartite using BFS coloring
(b) If bipartite, find the two partitions.
23. Color the following graph using the minimum number of colors:
Edges: (1,2), (2,3), (3,4), (4,1), (1,3)
(a) Show each step of the greedy coloring algorithm.
24. Consider a graph with the following adjacency matrix:
0 1 1 1 0
1 0 1 0 1
1
A= 1 0 1 1
1 0 1 0 1
0 1 1 1 0
Check whether the graph has an Euler path or an Euler circuit. If yes, construct it.
25. Let G be a bipartite graph with partitions (U, V), Where |U | = |V | = n, If every vertex in U is connected to
at least (n/2) vertices in V, prove that G has a perfect matching.