Discrete Mathematics: Solutions to Homework Assignment Problems

This document presents solutions to two discrete mathematics problems. The first solution addresses a problem involving the Pigeonhole Principle, demonstrating its application by analyzing the remainders when integers are divided by 4, and proving divisibility properties. The second solutio...Read More

Answers
Question 1
Let X be a non-empty set and it has a maximal element.
Let s4 be the maximal element of X, then s≤ s4 for all s∈ X and if for any y ∈ X with y ≥ s4 then y = s4,
We have the definition of supxs = least upper bounded of X
Then, a ≤¿xs for all a ∈ X
Since s4 is the maximal element with supxs ≥ s4.
We get that;
X4 = supxs
Using the principle of Pigeonhole
Since there are 4 possible when an integer is divided by 4 that at least one of n+1 integer in the set,
must have a remainder when divided 4, but if they have the same remainder when divided by 4, their
difference is divisible by 4
Hence in the set x1, x2, x3 and x4 there are one number xi and xj with i≠ j that have the same remainder
when they are divided by 4.
Thus, there exist k, m, r ∈ Nk , m, r , ∈ N with 0 ≤ r ≤ 4
Such that;
Xixj = 4k+ r =4 m +r
Xi = 4k+rxj = 4m+r
If we take their difference, we obtain
Xi – xj = (4k+r) – (4n+r) = 4k -4n = 4(k-m)
Therefore;
Xi – xixj – xj is divisible by 4
Points to note
Hence in the set x1, x2, x3 and x4 there are one number xi and xj with i≠ j that have the same remainder
when they are divided by 4.
Thus, there exist k, m, r ∈ Nk , m, r , ∈ N with 0≤ r ≤ 4
Such that;

Xixj = 4k+ r =4 m +r
Xi = 4k+rxj = 4m+r
If we take their difference, we obtain
Xi – xj = (4k+r) – (4n+r) = 4k -4n = 4(k-m)
Therefore;
Xi – xixj – xj is divisible by 4
I have used it to justify principle of Pigeonhole on testing if the set are divisible by any number,
holding most on the difference at the end, with a common factor as shown, this will guarantee a clear
demonstration of divisibility.
Just like in the calculation Xi – xj = (4k+r) – (4n+r) = 4k -4n = 4(k-m) the solution is found to have a
common factor of 4, meaning that it holds the divisibility of 4.

Question 2
Graph coloring
A graph “G” on finitely many vertices is a tree if and only if it is a maximal acyclic graph on those
vertices. Now suppose that the graph “G” on “n” vertices, has the property that every pair of vertices is
connected by a unique path. In order to prove that “G” is a tree, it suffices to show that that “G” is a
maximal acyclic graph on the vertices.
The first approach is to show that “G” is acyclic, suppose that this is not the case, so that there is a non-
trivial cycle in “G”, say;
μ0 - μ1 - μ2 -… - μn - μ0
then, there are two paths between the vertices μn and μ0 in “G”, namely;
μ0 - μ1 - μ2 -… - μn - μ0 and μn - μ0
but this contradicts the fact were the unique path that exists between any 2 vertices in “G”, this
contradiction must have occurred due to the only assumption we had made that “G” is not acyclic,
which must be false. Hence, G is acyclic.
Suppose “G” is another graph on the same set of vertices, such that E(G) E(G). assume that E(G)⫃
E(G”) so that there is an edge {μ, v}⫃ ∈ E ¿
Now, since u, v ∈V (G) there is a path μ - μ1 - μ2 -… - μn – v in E(G), but then, G” contains the
path
μ - μ1 - μ2 -… - μn – v - μ where the right most edge of G” is the addition edge that is assumed to have
existed in E ¿, but this last path is a cycle, which implies that G” is not acyclic, precisely G is tree.
Hence, if then we let P(n) be the proposition then every tree with “n” vertices is 2 colorable. The P(1) is
true, which is trivial
Suppose then that m is greater than 1 and that P(m) is true, having let G be a tree with m+1 vertices,
then G contains leaf x.
Let k be the vertex that is adjacent to x and let G” be the tree formed by removing x from G, then G” has
a two - coloring, and we extend this to G by coloring x a different color to k
In conclusion
Every tree is two- colorable.
Points to note
 n = number of vertices
 G = is the graph, with the path = μ0 - μ1 - μ2 -… - μn - μ0
 For one particular vertices 2 path can be traced which is μ0 - μ1 - μ2 -… - μn - μ0 and μn - μ0

 To avoid a contradiction brought about by two different path that exist been 2 vertices, we must
take the graph G be acyclic following one direction of the path.