Combinatorial ProofsPermutations and CombinationsPrecedence GraphsGraph TheoryCounting in Graph TheoryGraph ComplementsBipartite GraphsReading (Nothing to submit, but essential.)Homework 10The homework is due in class (during the first 10 minutes) on Thursday, 29th November (orbefore). The problems are mostly from the book by Rosen, 6th edition (sections 5.5, 9.1, 9.2). Asmentioned in the course syllabus, there are no electronic submissions and no late homeworks willbe accepted unless you have an illness spanning the full period from the time the homework wasassigned until it was due (and I shall need to see a medical practitioner’s certificate to that effect).Standard academic honesty rules apply. You can discuss problems with one another, but the solu-tions turned in should be entirely your own. Cases of plagiarism will be dealt with strictly. Also,make sure you write your name and section number on the first homework sheet andalso stapl e all the sheets together. UNSTAPLED OR UNNAMED HOMEWORKSWILL NOT BE GRADED.1 Combinatorial Proofs1. Section (5.4): 21(a).2. Prove that C(m + n, r) =Prk=0[C(m, r − k)C(n, k)] using a combinatorial argument.2 Permutations and CombinationsSection (5.5): 4, 18, 30.3 Precedence GraphsSection (9.1): 30, 31.4 Graph TheorySection (9.2): 5, 22, 24, 36(a),(e)1, 46.5 Counting in Graph TheorySection (9.2): 44, 45.1The question as to when exactly a given degree sequence is graphic, is quite interesting. Problems 38 to 41 ofsection (9.2) answer this question systematically. This is a challenging optional exercise for interested souls.16 Graph ComplementsSection (9.2): 53 (b),(c), 54, 57 (give a proper explanantion here :-))7 Bipartite GraphsSection (9.2): 58.8 Reading (Nothing to submit, but essential.)Read section (9.1) of the graph theory chapter to understand various applications of graph models.Section (9.2) for the c oncept of vertex degree, the Handshaking lemma (and its corollaries), thetypes of graphs (such as complete graph, cycle graph, wheel graph) and the concept of bipartitegraphs and theorems about the
View Full Document