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 solution delves into graph coloring, specifically proving that a graph is a tree if and only if it is a maximal acyclic graph. It further proves that every tree is two-colorable by induction, providing detailed explanations and points to note for each step. The solutions are designed to offer clarity and understanding of the mathematical concepts involved, making them ideal for students seeking help with their homework assignments.

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.