## MATH 363 Discrete Mathematics

#### email: firstname.lastname@ens.fr

 // home

## General notes

The midterm is short so it is unlikely that you will be asked anything which is too different and requires a proof.

Here, I have identified some relevant exercises but which may be in the wrong style. The midterm questions will be in the same style as the assignment questions (but a bit easier and with fewer questions).

You can always try to resolve some of the assignment questions (especially those you had difficulty with). You can also try to re-prove some of the lemmas and theorems seen in class.

## Logic

Solving problems that you did not chose in assignment 1.
Prove using rules of inference anything in the table of equivalence (replacing T by (not F)). It may be better to prove one direction first and then the other.

## Graph theory

### Rosen's book

Most of these are (too) easy (there will be some easy questions on the midterm). The starred questions are the right difficulty but because they are new, they would be (too) hard for the midterm (there will be some (most likely one) hard question on the midterm).
Also a good number of these are in the wrong "style", although they are on the correct topics (the midterm questions will be like the assignment questions).
• Ch 9.2 (p.608-611) 34,35,36,37,38,45,46,47,48,49,54,55,56,57,58
• Ch 9.4 (p.629-633) 1,2,6,26,28,29,30,31,34,35,43 (a cut vertex is a vertex whose removal disconnects the graph)
• Ch 9.5 (p.643-647) 1-11,13-15,30-43,26,44 (except Wn which we haven't seen),46,47,48,56-64,65
• Ch 9.6 (p.55-657) 2-14,17
I would also only try a random subset of these as some of them are too repetitive (maybe just pick one in that case).

### This book

Some of these are too difficult. Some of these are the right difficulty (but hard if they are new). They seem to more accurately reflect the style of the assignment and midterm questions.

You can also try to prove some of the things in this book that we have not proven (except for counting). Again, this is probably too hard for the midterm.

• Ch 7.1 (p.129) 7.1.2,7.1.4
• Ch 7.2 (p.133) 7.2.5,7.2.6,7.2.7,7.2.8,7.2.9,7.2.10
• Ch 7.3 (p.138-140) 7.3.1,7.3.2,7.3.3,7.3.4,7.3.10,7.3.11,7.3.12,7.3.14
• Ch 8.1 (p.145) all
• Ch 8.2 (p.145) 8.2.2,8.2.3
• Ch 8.5 (p.155) 8.5.3, 8.5.4 (a leaf is a vertex of degree 1),8.5.10
• Ch 9.1 (p 160) 9.1.1
• Ch 9.2 (p.163) 9.2.3, 9.2.4, 9.2.5

Website design modified from Sliqua taken from OSWD