discrete mathmatics

1. If your number n is odd, answer part (a) below. If it is even, answer part (b)
instead.
(a) Investigate the Sheffer stroke ↑ which represents the logical connective of alternative
denial, quoting at least two sources for the information you provide. In particular,
answer the following questions.
(i) Who was Sheffer?
(ii) When was the Sheffer stroke first described?
(iii) Is there an alternative symbol for the Sheffer stroke?
(iv) Represent each of the usual logical connectives of negation, conjunction, disjunction,
implication and equivalence in terms of alternative denial. (Show full working, and
make sure the Sheffer stroke is the only connective appearing in your final answers.)
(v) Explain the use of alternative denial in a practical application of Boolean algebra.
(Quote at least one source in your answer.)
(b) Investigate Peirce’s arrow ↓ which represents the logical connective of joint denial, quoting at least two sources for the information you provide. In particular, answer the
following questions.
(i) Who was Peirce?
(ii) When was Peirce’s arrow first described?
(iii) Is there an alternative symbol for Peirce’s arrow?
(iv) Represent each of the usual logical connectives of negation, conjunction, disjunction,
implication and equivalence in terms of joint denial. (Show full working, and make
sure Peirce’s arrow is the only connective appearing in your final answers.)
(v) Explain the use of joint denial in a practical application of Boolean algebra. (Quote
at least one source in your answer.)
(5 + 5 + 5 + 20 + 5 = 40 marks)
2. Let n be your special number. Consider the complete graph Kn on n vertices.
(a) Does Kn have a Hamilton circuit? If so, describe it. If not, explain why not.
(b) Does Kn have a non-cyclic Hamilton path? If so, describe it. If not, explain why not.
(c) Does Kn have an Euler cycle? Explain your answer.
(d) Does Kn have a non-cyclic Euler path? Explain your answer.
(4 × 5 = 20 marks)
3. Let n be your special number. Let p be the smallest prime divisor of n. Consider the complete
bipartite graph Kp,n.
(a) Does Kp,n have a Hamilton circuit? If so, describe it. If not, explain why not.
(b) Does Kp,n have a non-cyclic Hamilton path? If so, describe it. If not, explain why not.
(c) Does Kp,n have an Euler cycle? Explain your answer.
(d) Does Kp,n have a non-cyclic Euler path? Explain your answer.
(4 × 5 = 20 marks)
4. Let n be your special number. Let T be a free tree with n vertices.
(a) What is the least number of leaves that T can have? Explain your answer.
(b) What is the greatest number of leaves that T can have? Explain your answer.
(2 × 5 = 10 marks)
5. Let n be your special number. Let T be a binary rooted tree with n vertices.
(a) What is the least number of levels that T can have? Explain your answer.
(b) What is the greatest number of levels that T can have? Explain your answer.
(2 × 5 = 10 marks)
6. (a) Let n be your special number. Construct a map of a continent having n different
countries in such a way that four colours are needed to colour bordering countries in
different colours. Using blue for the ocean (and possibly for some of the countries), and
three other colours of your choice for the countries, apply colours to the map. [Use four
colours whose names start with different letters, so that you can represent each colour
with the first letter of its name.]
(b) By inserting vertices at strategic locations, convert your map into a connected planar
graph in which faces separated by an edge are differently coloured.
(c) Construct the dual graph of your connected planar graph, and apply the corresponding
vertex colouring to your dual graph.
(10 + 5 + 10 = 25 marks)