Discrete Mathematics Assignment: Solutions to Problems and Proofs

This document presents a comprehensive solution to a discrete mathematics assignment, tackling various problems across different areas of the subject. The assignment covers fundamental concepts such as logical connectives, truth tables, and quantifiers, with detailed solutions provided for each problem. It explores set theory, including Venn diagrams and set operations, and delves into graph theory, addressing topics such as adjacency tables, connected components, and graph equivalence. Furthermore, the assignment includes problems on mathematical induction, requiring students to prove or disprove statements and identify flaws in inductive arguments. The solutions are well-structured, providing clear explanations and justifications for each step, making it a valuable resource for students studying discrete mathematics. The document also includes examples of Eulerian walks, Hamiltonian cycles, and graph properties. The assignment covers a range of difficulty levels, providing a good overview of the topics covered in a typical discrete mathematics course.

Running head: DISCRETE MATHEMATICS 1
Discrete Mathematics
Name
Institution

DISCRETE MATHEMATICS 2
1. The logical connective “ NOT OR” denoted by , is true only when neither p nor q are true.
a. Write the truth table for p q.
p q p ↓ q
1 1 0
1 0 0
0 1 0
0 0 1
b. Write down the truth table for (p q) (p q).
p q p ↓ q p ↓ q (p ↓ q) ↓ (p ↓ q)
1 1 0 0 0
1 0 0 0 0
0 1 0 0 0
0 0 1 1 1
What do you notice?
The result for the (p ↓ q) is equivalent to (p ↓ q) ↓ (p ↓ q).
c. Show that both negation, as well as AND, can be written using only↓s.
“p and q”, denoted (p ∧ q)
p ~p q ~q (p ∧ q) (~ p ∧
~q)
1 0 1 0 1 0
1 0 0 1 0 0
0 1 1 0 0 0
0 1 0 1 0 1
Both negation as well as AND have only one truth instance.
2. Suppose we are considering all computers at Macquarie. Let P(x) is the statement “x is
connected to the network” and let Q(x) be the statement “x has at least 100 Terabytes of
storage”. Express each of the following sentences in terms of P(x), Q(x), quantifiers, and logical
connectives.
a) No computer at Macquarie is connected to the network, and also has at least 100 Terabytes of
storage.
Solution
∀x ¬P(x) ∧ ∃x ( Q(x))

DISCRETE MATHEMATICS 3
b) There is a computer at Macquarie which is either not connected to the network or has less than
100 Terabytes of storage.
Solution
∃x (¬P(x)) ∨ ∃x (¬Q(x))
3. Let P(x, y) be the proposition x2= y, where x and y are in the universe of integers.
Determine the truth value of each of the following propositions.
a. x P(6,x)ⱻ
Solution
This is not true; when x = −6, there is no y with y2= x = −6
b. x P(x,6)ⱻ
Solution
This is true; the rule y = x 2 determines a function, and hence the quantity y exists for any
x.
c. ꓯ x y P(x, y)ⱻ
Solution
This is true; the rule y = x 2 determines a function, and hence the quantity y exists for any
x.
d. yⱻ ꓯ x P(x, y)
Solution
This is not true; when x = −1, there is no y with y2= x = −1.
4. Prove or disapprove each of the following propositions.
a. If n2 is a multiple of 4, then n is a multiple of 4.
Solution
Consider n = 2. Then n2 = 4 = 4 · 1, so n 2 is a multiple of 4. However, n is not a multiple of 4.
b. If n3 is a multiple of 2, then n is a multiple of 2.
Solution
For n3 to be a multiple of 2, n = even number, hence n is divisible by 2 as all even numbers are
divisible by 2.

DISCRETE MATHEMATICS 4
5. Write down expressions for each of the shaded regions.
Solutions
In the first Venn diagram the piece from A is without its intersection with the union of B
and C, so is A − (B ∪ C). The remaining piece is the intersection of B and C without anything
from A, so is (B ∩ C) − A. In either case the symmetry between B and C is seen, since B ∪ C =
C ∪ B and B ∩ C = C ∩ B. Altogether, we have ( (B ∩ C) − A ) ∪ ( A − (B ∪ C) ) , retaining
this symmetry. For the second diagram we seek the union of the pairwise intersections; we can
take ( (A ∩ B) ∪ (A ∩ C) ) ∪ (B ∩ C), which displays symmetry upon swapping any pair of the
sets. The third diagram shows the union of A, B and C, minus what was shaded in the second
diagram. Thus we have (A ∪ B ∪ C) − ( (A ∩ B) ∪ (A ∩ C) ∪ (B ∩ C) ) ; which can be
alternatively written as ( A∪(B ∪C) ) \ ( ((A∩B)∪(A∩C))∪(B ∩C) ) , with extra parentheses to
emphasis the symmetry between B and C.
6. Suppose a relation is symmetric and transitive. Does that automatically make it reflexive?
If so explain why. If not, give a counter-example.
Solution
If xRy so that also yRx by the relation being symmetric. Since we also have transitivity,
then it looks like we would have xRx, giving reflexivity. However, consider the relation defined
on {0, 1, 2} given by R = {(0, 2),(2, 0),(0, 0),(2, 2)}. This is symmetric and transitive, but not

DISCRETE MATHEMATICS 5
reflexive — there is no (1, 1) element in the relation. Note that if every element was related to at
least one other, then reflexivity would indeed be deductible.
7. The following adjacent table for an undirected graph G is missing some information.
G
1 2 3 4 5 6 7 8 9
5 4 5 2 1 3 2 2 1
9 7 6 7 3 5 4 4 3
8 9 8 6 9 7 6
Explain how you could detect that it cannot possibly be complete. Correct it by adding the
minimal possible extra information, and then determine the number of connected components in
the graph, and the vertices in each connected component.
Solution
The adjacent table has some empty spaces without values. It should be complete to meet the
minimal requirements. Every element should appear once in a row and a column.
G
1 2 3 4 5 6 7 8 9
6 4 5 2 1 3 8 9 7
9 7 6 1 3 2 4 5 3
2 8 9 5 6 4 3 7 6
8. Determine the number of vertices for a simple graph which has 10 edges, two vertices of
degree 4 and all the other vertices of degree 3. Sketch an example of such a graph. Is it planar?
(There may be several non-isomorphic solutions.)
Solution
The sum of all degrees must be 20, so there must be (20 − 8)/3 = 4 vertices of degree 3. There
are two possible graphs, according to whether the vertices of degree 4 are adjacent or not.
9. Decide whether the two graphs G1 and G2 are equivalent, given their adjacency matrices as
below.

DISCRETE MATHEMATICS 6
G1 a b c d e f
a 0 1 1 1 0 0
b 1 0 1 0 0 1
c 1 1 0 0 0 0
d 1 0 0 0 1 0
e 0 0 0 1 0 0
f 0 1 0 0 0 0
And,
G2 u v w x y z
u 0 1 0 0 0 0
v 1 0 1 0 0 0
w 0 1 0 1 0 1
x 0 0 1 0 1 1
y 0 0 0 1 0 0
z 0 0 1 1 0 0
If not, explain why they cannot be equivalent. If so, draw the graph and label each vertex
with the label of the row it corresponds to in the first matrix in blue and the label of the row it
corresponds to in the second matrix in red.
Solution
Both graphs have 6 edges. The vertex degrees are for G1: {3, 3, 2, 2, 1, 1} while for G2: {1, 2, 3, 3, 1,
2}. Vertices can be matched up 1–1 only as shown at right. This is found by noting that each graph
has a single vertex of degree 1 (f and y) which is adjacent to a vertex of degree 3 (b and x). The other
vertex of degree 1 (e and u) is adjacent to a vertex of degree 2 (d and v). The remaining associations
are then determined by the degrees of the vertices. Confirm all adjacencies.
10. Seven towns labeled A, B, C, D, E, F and G are connected by a system of freeways as
follows:
i. F1 goes from A to E, passing through D;
ii. F2 goes from E to G and then passes through D as it continues to F;
iii. F3 goes from G through C to A;
iv. F4 goes from F to D, passing through B;

DISCRETE MATHEMATICS 7
v. F5 goes from B to G.
a. Using vertices for towns and edges for the freeway sections between towns draw a graph
which models this situation.
Solution
b. List all the simple paths from E to F, which do not pass through any city more than once.
Solution
g-> a;
g-> b ->c-> d-> e-> a
g-> d->e->a
d. What is the smallest number of freeway sections which would need to be closed to
prevent travel from D to G?
Solution
b-> d =2 we take cut b->c->d
11. a. Prove that G= (V, E) has no Eulerian walk, where the vertices are V= {a, b, c, d, e, f}
and the edges are E = {ab, ac, bc, ce, de, df, ef}.
Solution
The degrees of each vertex are respectively: 3, 2, 3, 2, 3, 3. Since there are more than 2 odd-
degree vertices, there can be no Euler walk. A graph can be drawn as shown below;

DISCRETE MATHEMATICS 8
Show that it is possible to add one edge to G to form a simple graph that does have an Eulerian
walk, and find such a walk. There may be more than one way to do this.
Solution
Add an edge between two odd-degree vertices, where no edge currently is present; either ef or ac
works. These are shown dotted in the graph above.
Adding ef gives an Euler walk such as: c → d → f → c → e → f → a → b → e → a and
other possibilities. Adding ac gives an Euler walk such as: f → d → c → a → b → c → e
→ b → a → e, and other possibilities.
b. Show that G = (V, E) has no Hamiltonian cycle, where the vertices are V= {a, b, c, d, e, f, g}
and the edges are E = {ab, ac, bc, bd, cd, de, df, ef, eg, fg}.
Solutiom
A graph is shown at right. Removing the vertex d disconnects it into 2 connected components
{a, b, c} and {e, f, g}. So it is not possible to construct a closed walk visiting both components
without going multiply through vertex d; but such a path cannot be Hamiltonian. Even starting at
d allows a Hamiltonian path within each component, but this must return to d before the other
component can be visited.
12. What is wrong with the following “proof” by Mathematical Induction?
We will prove statements that all computers are built by the same manufacturer. In particular, we
prove statements B (n) with n N, that “in any collection of n computers, all of the computers areꞓ
built by the same manufacturer”.
First check that B (1) is true, since with only one computer there is only one manufacturer. Now
assume B (k); that is, in any collection of k computers, all are built by the same manufacturer. To
prove B (k + 1) consider any collection of k + 1 computer. Pull out one of these computers,
‘HAL” say, leaving just k computers, all of which must have the same manufacturer.

DISCRETE MATHEMATICS 9
Swap the ‘HAL’ computer with one of the others, so again there are k computers, so all must
have the same manufacturer. Thus ‘HAL’ must have the same manufacturer as others, hence all
k+1 computers have the same manufacturer; that is B (k+1) must be true.
Solution
If you take out one, you get a set A of k computers, and if you take out another, you get a
different set B of k computers.
But the assumption is that A∩B is not empty - that they have an element in common.
That is not true when k+1=2. Then A and B are singleton sets, and they are disjoint. So it is true
that A is a set all made by one manufacturer, and B is a set all made by one manufacturer. To
conclude that A∪B was all made by one manufacturer, A and B must have a common element.