COMP1805ABC (Winter 2024) -“Discrete Structures I”
Carleton
University
• Your assignment should be typed and submitted online as a single .pdf file, created using Google Docs,
Microsoft Office, or LaTeX. Handwritten submissions (including those that have been scanned or photographed)
are not acceptable and will receive a mark of zero. Compressed files (e.g., "zip", "rar”, “tar", etc.) or documents
in another format (e.g., “doc”, “docx”, “rtf”, “txt”, “jpg", etc.) will be penalized and may receive a mark of
zero.
• When you submit your assignment to Gradescope, you MUST assign questions to pages. For every question
that is not assigned to a page or is assigned to the wrong page, you will receive a penalty of 50% of the
question mark. For example, if Q2, worth 10 points, was misassigned, then your max grade for Q2 will be 5
points.
• Late assignments will be accepted for up to 12 hours after the deadline without penalty. No late assignments
will be accepted after that.
• Write down your name and student number on every page. You can use header settings for that.
• Start each question on a new page. The questions should be answered in order.
• Each response should begin with a principal answer (for example, the final formula, True/False, Yes/No,
etc.) followed by your explanation/solution starting from a new line.
• You need to show your work, but also keep your solution precise, concise and clear. A correct solution will
receive partial mark if it is not accompanied by the work required to reach it.
• If you do not know how to produce some formula or indentation, please ask the teaching team. We will help
you. Poor formatting will be penalized. Examples are: no indentation; no spaces between parts/questions;
no question numbers; specifying negation (¬) by "not", "-", etc; writing compliment sign (A) as anything but
the proper sign, or letting it hover a line (or more) above (A).
• Marks for every question are specified at the beginning of every question. The grading scheme for each question
is “full marks" for correct answer, “half marks” for an answer that is not completely correct and 0 otherwise.
1. (18pts) Below, you are given the sequence of the degrees of vertices of a simple undirected graph G. For each
of the sequences, determine whether G is feasible or not. If the graph is feasible, state its name (such as K4,
K3,3, C5, etc.), and list the main properties (such as connected/disconnected, planar/non-planar, bipartite or
not, tree, etc.). If it is not feasible, explain why, using graph properties, definitions, Handshaking Lemma, or
theorems we proved in class.
(a) 5,5,5,5,5,5
(b) 1,1,1,1,1,5
(c) 1, 2, 2, 3, 3, 4, 6
(d) 2,2,2,3,3,6
(e) 2,2,3,3,3,5
(f) 1,2,3,4,4
(g) 0,2,2,2,4
(h) 3, 3, 3, 3, 3, 3
(i) 1, 1, 1, 1, 1, 1 6.
COMP1805ABC (Winter 2024) -“Discrete Structures I”
Assignment 5 of 5 - Due Monday April 8, 23:59
Carleton
University
2. (8pts) Draw the following graphs using the software of your choice. You must use the templates Q2(a) and
Q2(b) provided with the assignment (see below). For your convenience, I added the templates in three formats:
.pdf, .png, and .ipe. To create the templates, I used the Ipe extensible drawing editor https://ipe.otfried.org/.
It is the best choice for LaTeX, and it is free. You can open my .ipe files, add the necessary edges to the graphs,
and save them as .pdf files. If you are using my LaTeX source for the assignment, then after compiling it, you
will see the updated images inserted into the resulting .pdf.
(a) Undirected graph represented by the adjacency list:
1:
2, 6, 9
2:
1, 3, 9
3:
2, 4, 8
4:
3, 5, 8
5:
4, 6, 7
6:
1, 5, 7
7:
5, 6, 8, 9, 10
8:
3, 4, 7, 9, 10
9:
1, 2, 7, 8, 10
10:
7, 8, 9
(b) Directed graph represented by the adjacency matrix:
The templates:
1.
9
10.
500
2
1
00
0
100
0
0
0 0
1 0
0 1
100
1 0
1
000
0 1
0 0
0
1
0
1 0 0
0 0 0
0 0 1 0 0
00 0 1 0
0 0 0
00 0
00 0 0
0
0 0 0
0 1 0 1
0
1. 7.
сто
(a)
(b)
6
එය COMP1805ABC (Winter 2024) -“Discrete Structures I"
Assignment 5 of 5 - Due Monday April 8, 23:59
Carleton
University
3. (15pts) Prove or disprove the following statements about simple undirected graphs:
(a) There exists a graph with chromatic number 4, whose maximal clique number is strictly smaller than 4.
(b) The only graph whose BFS and DFS trees are identical (no matter which starting vertex is selected) is
the tree itself.
(c) Five houses cannot be connected to the sources of water and electricity without connections crossings.
4. (15pts) Decide whether an adjacency matrix or adjacency lists would be more efficient for storing each of the
graphs presented. Justify your decision for each graph.
(a) Cn. We will add/remove no more than n/7 edges daily, and restore the graph on Mondays. Another most
common operation we will do is we will check for an edge between vi and vj.
(b) Kn. We will remove around n edges every weekday and restore the graph over a weekend. We will often
ask to retrieve (or output) all the neighbours of a particular vertex.
(c) Kn,5. We will colour some of the edges blue, yellow, or magenta and often check whether a vertex v; has
at least one edge of each colour.
(d) An undirected graph with a vertex for every person in the world. We will use it to model whether two
people are siblings.
(e) A directed graph that contains a vertex for every active website. We will use it to model whether one
website contains a link to another.
5. (6pts) Prove using induction that every tree on n ≥ 2 vertices is bipartite. Recall that in class, we proved
that every tree with n ≥ 2 vertices has at least 2 vertices of degree 1. You can use this fact in your proof.
6. (12pts) Prove each of the following statements using mathematical induction.
(a) Prove that for all n ≥ 1, Σi±1 i(i+1)
n
n+1°
(b) Prove that for all integers n > 7, n²/2 − 5n + 8 is non-negative.
7. (9pts) Provide a recursive definition of the following sequences {an}, n = 1, 2, . . .. Refer to the sample solution
in part (a).
(a) an
= 5n
Solution: Using the definition an
= 5n we derive: a₁ =
An
5n
5n+5 5
=
(5n5)+5
=
an-1+5
Recursive Dfn: a₁ =
: 5 and an = an−1 +5, Vn ≥ 2.
(b) an
= 15
(c) an = 7n - 9
= 5(n − 1) = 5n — 5.
5; and an-1=
definition of an
adding zero (5 – 5)
associative/commutative laws
definition of an-1
(d) an = 3n² n
8. (12pts) Determine if the following relations are reflexive, symmetric, anti-symmetric, or transitive. Justify your
answer. For each relation, conclude whether it is an equivalence relation, partial ordering, or neither. Part
(a) of the question contains a sample solution. Follow the provided solution format for the other parts of the
question. COMP1805ABC (Winter 2024) -“Discrete Structures I”
Assignment 5 of 5 - Due Monday April 8, 23:59
(a) R₁ = {(a, b) | [a] = [b]} defined on the set of real numbers.
Solution:
Reflexive: yes, since [a] = [a] is true for all real numbers.
Carleton
University
Symmetric: yes. Suppose (a, b) = R and thus [a] = [b]. Since [a] = [b], we have [b] = [a]. Therefore,
(b, a) Є R.
Anti-symmetric: no. We can have (a,b) = R and (b, a) = R for distinct a and b. For example,
[1.1] = [1.8] = 1, and thus (1.1, 1.8) € R and (1.8, 1.1) € R. But 1.1 ± 1.8.
Transitive: yes. Suppose [a]
follows that [a] = [c].
=
[b] and [b]
=
[c]. From transitivity of equality of real numbers, it
Since the relation is reflexive, symmetric, and transitive, it is an equivalence relation.
(b) R2 = {(a, b) | [a] ≤ [b]} defined on the set of real numbers.
(c) R3 = {(a,b) | 2 ≥ |a – b|} defined on the set of real numbers.
-
(d)_R₁ = {(a,b) | a + b is odd } defined on the set of integers.
9. (5pts) Use topological sort to assist the three heroes below in getting dressed.
hood
hood
cape
gauntlets
tiara
breastplate
shirt
belt
underpants
loin cloth
corset
bracelets
boots
tights
boots shoulder pads
shorts
boots
underpants
Skeletor
Wonder Woman
Batman
