21ODMCT614-Discrete Mathematical Structure

Combinatory 1 93 The Rules of Sum and Product
The Rule of Sum − If a sequence of tasks T1, T2, …, Tm can be done in w1, w2, … wm ways respectively (the condition is that no tasks can be performed simultaneously), then the number of ways to do one of these tasks is w1 + w2 + … + wm. If we consider two tasks A and B which are disjoint (i.e., A ∩ B =  A ∩ B =  ), then mathematically |A∪B|=|A|+|B||A∪B|=|A|+|B|
The Rule of Product − If a sequence of tasks T1, T2, …, Tm can be done in w1, w2, … wm ways respectively and every task arrives after the occurrence of the previous task, then there are w1 × w2 × ... × wm ways to perform the tasks. Mathematically, if a task B arrives after a task A, then | A × B | = | A | × | B | | A × B | = | A | × | B | Example 4: A boy lives at X and wants to go to School at Z. From his home X he has to first reach Y and then Y to Z. He may go X to Y by either 3 bus routes or 2 train routes. From there, he can either choose 4 bus routes or 5 train routes to reach Z. How many ways are there to go from X to Z? Solution: From X to Y, he can go in 3 + 2 = 5 ways (Rule of Sum). Thereafter, he can go Y to Z in 4 + 5 = 9ways (Rule of Sum). Hence, from X to Z he can go in 5×9 = 45 ways (Rule of Product). 6.5 Permutations Definition: An arrangement of some or all of a given number of things in order is called permutation. The total number of permutations of n different things taken r at a time is denoted by nPr or P(n, r). e.g., (1) 5C2 or P(5, 2) means the number of permutations of 5 things taken 2 at a time. (2) 6P3 means the number of permutations of 6 things taken 3 at a time. npr = n! (n  r)! CU IDOL SELF LEARNING MATERIAL (SLM)

94 Discrete Mathematical Structures Factorial Notation: In above formula for nPr, we see that we need to write the product of consecutive integer. To express the product of consecutive integers factorial notation is very convenient. The product 1. 2. 3. 4. …, n is denoted by n! or Ln (read as n factorial or factorial n). Example: (1) 10! = 1. 2. 3. 4. 5. 6. 7. 8. 9. 10 (2) 5! = 1.2.3.4.5 n! = n(n – 1)! and (n + 1).n! = (n + 1)! Corollary: The number of permutations of n different things taken all at a time is npn = n!,. The number npn can be obtained by putting r = n in the npr formula. npn = n! n! (n  n)!  o! Note: From the definition of n!, it appears that 0! is meaningless. However, if we put r = n, we get npn = n! . o! But we know that npn = n!. In order to make the two results agree we define 0! = 1. Example 5: Find the value 5p2 and interpret the answer obtained. Solution: 5p2 = 5!  5!  5  4 3!  5  4  20  2)! 3! 3! (5 Example 6: How many different ways the letters of the word BOARD can be arranged? How many of these words begin with ‘R’? How many words can be formed using the letters of the word ‘BOARD’ taken 3 at a time? Solution: The word ‘BOARD’ consists of 5 different letters B, O, A, R, D. These 5 different letters can be arranged amongst themselves in 4p5 = 5! = 120 ways. CU IDOL SELF LEARNING MATERIAL (SLM)

Combinatory 1 95 If the word begins with R, then remaining four letters can be arranged amongst themselves in 4p4 = 4! = 24 ways. From given 5 different letters, any three different letters can be arranged in 5p3 = 5!  5! = 60 ways. (5  3)! 2! Example 7: How many 2 digits number can be formed with the digits 3, 5, 6, 7, 8, if none of the digits is being repeated in any of the numbers so formed? Solution: Here n : 5, and we have to find the number of permutations of 2 different digits taken at a time. This can be done in 5p2 ways. Total number of 2 digit numbers. = 5p2 = (5 5!  5! = 20 ways.  2)! 3! OR 2 digits number consists of unit’s place and 10’s place. 10’s place can be filled by any one of the five given digits in 5 different ways. Since, both the digits should be different, unit’s place can be written in 4 ways.  Using fundamental principle of multiplication, these two places can be filled in 5 × 4 = 20 ways. 6.6 Combinations Definition: A selection (group) of number of things (objects) taking some or all of them at a time is called combination. The total number of combinations of n distinct things taking r (1 ≤ r ≤ n) at a time is denoted by nCr or C(n, r) or  nr  . CU IDOL SELF LEARNING MATERIAL (SLM)

96 Discrete Mathematical Structures Example: Selection of two students from a group of five students will be represented by 5C2 or  52  or (5, 2). Theorem 1: Total number of combinations or selection of n different objects taken r at a time is given by n Cr  n! r)! r!(n  Proof: Each combination consists of ‘r’ different things and these r things can be arranged amongst themselves in rpr = r! way. Thus, the number of arrangements corresponding to the nCr combination is nCr x r! nCr × r! = npr n Cr  n pr r!(n  r)! n Cr  n! r)! r!(n  Note: (1) nCo = nCo = 1 (2) nCn = 1 (3) nCr = nCn–r Proof: nCn–r  (n n!  r)![n  (n  r)]!  (n n!  r)!r! n C(nr)  nCr ,1 ≤ r ≤ n CU IDOL SELF LEARNING MATERIAL (SLM)

Combinatory 1 97 6.7 Principle of Inclusion-Exclusion For Two sets: Let A and B be finite sets then principle of Inclusion-Exclusion for two sets is given by, |A∪B|=|A|+|B|–|A∩B| For Three sets: Let A, B and C be finite sets then principle of Inclusion-Exclusion for three sets is given by, |A∪B∪C|=|A|+|B|+|C|–|A∩B|–|A∩C|–|B∩C|+|A∩B∩C| Example 8: Find number of integers between 1 and 2100 that are divisible by 2 or 3 or 7. Solution: Let A = set of integers between 1 and 2100 divisible by 2 B = set of integers between 1 and 2100 divisible by 3 C = set of integers between 1 and 2100 divisible by 7 Total number of integers between 1 and 2100 = 2098 CU IDOL SELF LEARNING MATERIAL (SLM)

98 Discrete Mathematical Structures By principle of Inclusion-Exclusion for three sets |A∪B∪C| =|A|+|B|+|C|–|A∩B|–|A∩C|–|B∩C|+|A∩B∩C| = (1049 + 699 + 299) – (349 + 149 + 99) + 49 = 2047 – 597 + 49 = 1499  1499 numbers are divisible by 2 or 3 or 7 between 1 and 2100. Example 9: Determine the number of integers from 1 and 250 that are divisible by any of the integers 2, 3, 5 and 7. Solution: Let U = {1, 2, 3, …………………………, 250} | U | = 250 A = The set of numbers in U that are divisible by 2 B = The set of numbers in U that are divisible by 3 C = The set of numbers in U that are divisible by 5 D = The set of numbers in U that are divisible by 7 CU IDOL SELF LEARNING MATERIAL (SLM)

Combinatory 1 99 Now by principle of Inclusion-Exclusion, |A∪B∪C∪D| =|A|+|B|+|C|+|D|–|A∩B|–|A∩C|–|A∩D|–|B∩C| – | B ∩ D| – | C ∩ D | + | A ∩ B ∩ C | + | A ∩ B ∩ D | + | A ∩ C ∩ D | + | B ∩ C ∩ D | –| A ∩ B ∩ C ∩ D | = 125 + 83 + 50 + 35 – 41 – 25 – 17 – 16 – 11 – 7 + 8 + 5 + 3 + 2 – 1 = 208 Example 10: A survey of 500 students taking one or more courses in algebra, physics and statistics during one semester revealed the following numbers of students in the indicated subjects: Algebra 329 Algebra and Physics 83 Physics 186 Algebra and Statistics 217 Statistics 295 Physics and Statistics 63 CU IDOL SELF LEARNING MATERIAL (SLM)

100 Discrete Mathematical Structures How many students were taking? (a) All three subjects? (b) Algebra but not statistics? (c) Physics but not algebra? (d) Statistics but not physics? (e) Algebra or statistics but not physics? (f) Algebra but not physics or statistics? Solution: Let A denote the set of all students taking a algebra. P denote the set of all students taking a physics. S denote the set of all students taking a statistics. Given : | A ∪ P ∪ S | = 500, | A | = 329, | P | = 186, | S | = 295, | A ∩ P | = 83, | A ∩ S | = 217, | P ∩ S | = 63 Algebra Physics 30 93 82 53 164 10 68 Statistics (a) By principle of Inclusion-Exclusion, we have |A∪P∪S|=|A|+|P|+|S|–|A∩P|–|A∩S|–|P∩S|+|A∩P∩S| 500 = 329 + 186 + 295 – 83 – 217 – 63 + |A ∩ P ∩ S|  | A ∩ P ∩ S | = 53 (b) Algebra but not statistics = | A | – | A ∩ S | – | A ∩ P ∩ S| = 329 – 164 – 53 CU IDOL SELF LEARNING MATERIAL (SLM)

Combinatory 1 101 = 112 (c) Physics but not algebra = 93 + 10 = 103 (d) Statistics but not physics = 68 + 164 = 232 (e) Algebra or statistics but not physics = 82 + 164 + 68 = 314 (f) Algebra but not physics or statistics = 82 6.8 Recurrence Relation A relation which can be obtained by using its previous terms with specifying initial conditions is called recurrence relation. For Example: Consider a sequence {an} = {1, 5, 9, 13, ……} In the above sequence each term is generated from the previous value. When n = 1, a1 = 1 When n = 2, a2 = 1 + 4 = 5 = a1 + 4 When n = 3, a3 = 5 + 4 = 9 = a2 + 4 . .  an = an – 1 + 4 The above equation is a recurrence relation which is obtained by its previous terms. Definition: A linear homogeneous recurrence relation of degree k with constant coefficients is a recurrence relation of the form an = c1 an – 1 + c2 an – 2 + ……. + ckan–k Where c1, c2, c3,…………….,ck are real numbers and ck ≠ 0. CU IDOL SELF LEARNING MATERIAL (SLM)

102 Discrete Mathematical Structures Degree of the recurrence relation is k because an is expressed in terms of the previous k terms of the sequence. Example 11: Find first four terms of the sequence defined by the given recurrence relation. an = an–1 + 2 an–2 with a0 = 0, a1 = 2 Solution: We have an = an–1 + 2 an–2 with a0 = 0, a1 = 2 put n = 2, a2 = a1 + 2 a0  a2 = 2 + 2 . 0 = 2. 6.9 Summary of the Unit
The Chapter offers information on introductory examples, permutations and combinations, and the inclusion-exclusion principle. Discussions focus on some applications of the inclusion-exclusion principle, derangements, calculus of sets, permutations, combinations, stirling's formula, binomial theorem, regions of a plane, chromatic polynomials, and a random walk. The text then examines linear equations with unit coefficients, recurrence relations, and generating functions.
Infinite sets are very peculiar, and remarkably different from finite sets. This can be illustrated with a combinatorial example. Suppose, we have four pigeons and two pigeonholes. If we place the pigeons in the pigeonholes, one of the pigeonholes must contain at least two pigeons. This crowding will always occur, regardless of the arrangement, we choose for the pigeons.
In mathematics, permutation relates to the act of arranging all the members of a set into some sequence or order, or if the set is already ordered, rearranging its elements, a process called permuting. Permutations occur, in more or less prominent ways, in almost every area of mathematics. They often arise when different orderings on certain finite sets are considered. CU IDOL SELF LEARNING MATERIAL (SLM)

Combinatory 1 103
The combination is a way of selecting items from a collection, such that (unlike permutations) the order of selection does not matter. In smaller cases, it is possible to count the number of combinations. 6.10 Key Words/Abbreviations
Mathematical induction: A technique for proving results or establishing statements for natural numbers.
Combination: An arrangement of objects where order does not matter.
Permutation: The act of arranging the members of a set into a sequence or order.
Factorial: The product of all the positive integers equal to and less than your number.
Recurrence relation: An equation that uses recursion to relate terms in a sequence or elements in an array. 6.11 Learning Activity 1. Explain Mathematical Induction. ----------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------- 2. Describe Inclusion-Exclusion Principle. ----------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------- 3. Describe Recurrence Relations. ----------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------- 4. Describe the Concept of Permutations, Combinations. ----------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------- CU IDOL SELF LEARNING MATERIAL (SLM)

104 Discrete Mathematical Structures 6.12 Unit End Questions (MCQ and Descriptive) A. Descriptive Types Questions 1. Prove that 2 + 4 + 6 + ... + 2n = n2 + n, For all integers n ≥ 1. 2. A sequence a1, a2, a3, ... is defined by letting a1 = 3 and an = 7an − 1 for all integers n ≥ 2. Show that an = 3 • 7n − 1 for all integers n ≥ 1. 3. Suppose, there are 26 male and 16 female professors to teach Discrete mathematics. In how many ways a student can choose Discrete mathematics professor. 4. In how many different ways can a housing society elect a president, treasurer and secretary out of 15 members? 5. A coin is tossed 7 times. In how many different ways can we obtain (a) 4 heads and 3 tails (b) At least 5 heads 6. How many distinct 5-digit numbers can be formed using the digits 3, 4, 3, 4, 2? 7. A survey of 500 television watchers produced the following information: 285 watch cricket, 195 watch hockey, 115 watch tennis, 45 watch cricket and tennis, 70 watch cricket and hockey, 50 watch hockey and tennis, 50 do not watch any of the 3 games. (i) How many people in the survey watch all the 3 games? (ii) How many people watch exactly 1 of the three games? B. Multiple Choice/Objective Type Questions 1. There are 30 people in a group. If all shake hands with one another, how many handshakes are possible? (a) 870 (b) 435 (c) 30! (d) 29! + 1 CU IDOL SELF LEARNING MATERIAL (SLM)

Combinatory 1 105 2. How many words can be formed by using letters of word ALIVE? (a) 86 (b) 95 (c) 105 (d) 120 3. There are 2 vegetarian dishes options and 5 non-veg option on a dinner menu.What is the total number of option? (a) 5 (b) 6 (c) 7 (d) None of these 4. A student wants to buy a new computer, if there are 3 desktops and 4 laptops of different companies available. (a) 5 (b) 6 (c) 12 (d) 7 5. An arrangement of some or all of a given number of things in order is called __________. (a) Permutation (b) Combination (c) Sum rule (d) Product rule Answers 1. (b), 2. (a), 3. (c), 4. (d), 5. (a) 6.13 References References Book: 1. http://home.iitk.ac.in/~arlal/book/mth202.pdf Web Resources: 1. https://socratic.org/questions/what-are-combinatorics-in-discrete-mathematics 2. https://www.tutorialspoint.com/discrete_mathematics/discrete_mathematics_counting_ theory.htm 3. https://www.tutorialspoint.com/discrete_mathematics/discrete_mathematics_recurrence_ relation.htm CU IDOL SELF LEARNING MATERIAL (SLM)

UNIT 7 COMBINATORY 2 Structure: 7.0 Learning Objectives 7.1 Introduction 7.2 Recurrence Relation 7.3 Homogeneous Recurrence Relations 7.4 Non-homogeneous Linear Equations 7.5 Generating Function 7.6 Recurrence Relation by the Method of Generation Functions 7.7 Solution of Combinatorial Problem using G.F. 7.8 Summary 7.9 Key Words/Abbreviations 7.10 Learning Activity 7.11 Unit End Questions (MCQ and Descriptive) 7.12 References 7.0 Learning Objectives After studying this unit, you will be able to:
Define Homogeneous and Non-homogeneous recurrence relations.
Define Generating Function.

Combinatory 2 107
Find Solution of Recurrence relation using G.F.
Explain the properties of G.F. 7.1 Introduction In this chapter, we will discuss how recursive techniques can derive sequences and be used for solving counting problems. The procedure for finding the terms of a sequence in a recursive manner is called recurrence relation. We study the theory of linear recurrence relations and their solutions. Finally, we introduce generating functions for solving recurrence relations. 7.2 Recurrence Relation A relation which can be obtained by using its previous terms with specifying initial conditions is called recurrence relation. For Example: Consider a sequence {an} = {1, 5, 9, 13,……} In the above sequence each term is generated from the previous value. When n = 1, a1 = 1 When n = 2, a2 = 1 + 4 = 5 = a1 + 4 When n = 3, a3 = 5 + 4 = 9 = a2 + 4 . .
an = an – 1 + 4 The above equation is a recurrence relation which is obtained by its previous terms. 7.3 Homogeneous Recurrence Relations Definition: A linear homogeneous recurrence relation of degree k with constant coefficients is a recurrence relation of the form CU IDOL SELF LEARNING MATERIAL (SLM)

108 Discrete Mathematical Structures an = c1 an – 1 + c2 an – 2 + ……. + ck an – k Where c1, c2, c3,……, ck are real numbers and ck  0. Degree of the recurrence relation is k because an is expressed in terms of the previous k terms of the sequence. Example 1: Find first four terms of the sequence defined by the given recurrence relation, an = an – 1 + 2 an – 2 with a0 = 0, a1 = 2. Solution: We have an = an – 1 + 2an – 2 with a0 = 0, a1 = 2 put n = 2, a2 = a1 + 2a0  a2 = 2 + 2 . 0 = 2 a3 = a2 + 2a1 = 2 + 2 . 2 = 2 + 4 = 6
The first four terms are 0, 2, 2, 6. Example 2: Find the degree of the given recurrence relations (a) an = 3an – 1 + 4an – 2 + 5an – 3 (b) an = an – 1 + an – 4 Solution: (a) degree is 3 (b) degree is 4 Explicit Formula: An equation used to represent the nth term of the sequence is called an explicit formula or general solution of recurrence relation. Consider the sequence 7, 21, 63, …………..we will find the general solution of the sequence. The equation an + 1 = 3an, n ≥ 0 is the recurrence relation of the above sequence as the value of an + 1 is dependent on an. CU IDOL SELF LEARNING MATERIAL (SLM)

Combinatory 2 109 Now an + 1 = 3an, n ≥ 0, a0 = 5 On substituting the values of n, we get a1 = 3a0 = 3 . 5 a2 = 3. a1 = 3. 3.5 = 32.5 a3 = 3. a2 = 3 . 32 .5 = 33.5 It suggest that for each n ≥ 0 an = 3n.5 = 5. 3n an = 5(3n) is called the general solution of the given recurrence relation. In general solution, the value of an is a function of n and there is no longer any dependence on previous terms of the sequence. To compute a10 we use the general solution a10 = 5. (310) = 295,245. There is no need to start from a0 and build up to a9 in order to obtain a10. There are three methods to solve recurrence relation: I. Backtracking method. II. Characteristic root method. III. Using Generating function. I. Backtracking Method or Iterative approach: Example 3: Solve an = 7an – 1 for n ≥ 1 and a2 = 98 Solution: Since, an = 7an – 1 Therefore, an – 1 = 7an – 2 an – 2 = 7an – 3 an – 3 = 7an – 4 and so on… Now, substitute the above equations in the given recurrence relation CU IDOL SELF LEARNING MATERIAL (SLM)

110 Discrete Mathematical Structures an = 7an – 1 = 7(7an – 2) = 72an – 2 = 7(7.(7an – 3) = 73an – 3 = 73(7an – 4) = 74(an – 4) We can generalize an = 7r(an – r) Put n – r = 2  an = 7n – 2(a2) = 7n – 2(98)  an = 7n – 2 × 72 × 2  an = 7n 2 The general solution is an = 7n 2. Example 4: Solve the recurrence relation using backtracking method. an = 2an – 1 + 3, n ≥ 2a1 = 5 Solution: Since, an = 2an – 1 + 3, Therefore, an – 1 = 2an – 2 + 3 an – 2 = 2an – 3 + 3 an – 3 = 2an – 4 + 3 an – 4 = 2an – 5 + 3 Now, substitute the above equations in the given recurrence relation an = 2an – 1 + 3 = 2(2an – 2 + 3) + 3 = 2.2an – 2 + 2. 3 + 3 = 2.2 (2an – 3 + 3) + 2. 3 + 3 = 2.3 an – 3 + 2.2.3 + 2. 3 + 3 .. CU IDOL SELF LEARNING MATERIAL (SLM)

Combinatory 2 111 . . = 2r an – r + 3(2r – 1 + 2 r – 2 + … + 22 + 2 + 20) = 2r an – r + 3(20 + 21 + 22 + 23 + … + 2r – 1) Since, sum of geometric progression is Sr = a((common ratio)no. of terms – 1)/(common ratio – 1) = 2r an – r + 3 (1(2r – 1)/(2 – 1)) = 2r an – r + 3 (2r – 1) Put n – r = 1  an = 2n – 1 + 3(2n – 1 – 1)  an = 2n – 1 + 3 (2n – 1 – 3)  an = 4. 2n – 1 + 3 is the general solution. Example 5: an = an – 1 + n, a0 = 0 Solution: Since, an = an – 1 + n Therefore, an – 1 = an – 2 + n – 1 an – 2 = an – 3 + n – 2 an – 3 = an – 4 + n – 3 Hence, an = an – 1 + n = an – 2 + n – 1 + n = an – 3 + n – 2 + n + n – 1 = an – 4 + n – 3 + n – 2 + n + n – 1 CU IDOL SELF LEARNING MATERIAL (SLM)

112 Discrete Mathematical Structures = an – 4 + 3n – 3 – 2 – 1 . . . = an – r + (r – 1)n – (r – 1) Let n – r = 0 ⇒ n = r = a0 + n(n – 1) – n(n – 1)/2 a0 = 0 (initial condition) = n(n – 1)/2 Example 6: Suppose that a person deposits ` 10,000 in a savings account at a bank yielding 12% per year with interest compounded annually. How much will be there in account after 30 years? Solution: Let Pn denotes the amount in the account after n years, i.e., the amount in n years along with 12% interest on the amount after n years. Therefore, Pn = Pn – 1 + 0.12 Pn – 1 = 1.12 Pn – 1 The initial condition is P0 = 10,000 We use backtracking method to solve the recurrence relation. P1 = 1.12 P0 P2 = 1.12 P1 = (1.12)2 P0 P3 = 1.12 P2 = (1.12)3 P0 . . CU IDOL SELF LEARNING MATERIAL (SLM)

Combinatory 2 113 . Pn = 1.12 Pn – 1 = (1.12)n P0 P0 = 10,000 Therefore, Pn = (1.12)n 10,000 When n = 30, P30 = (1.12)30 – 10,000 II. Characteristic root method: There are two types of recurrence relations, linear and non-linear relations. The recurrence relation an + 1 – an = 0 is called linear because each subscripted term appears to the first power. The recurrence relation an + 1 – 3an. an – 1 = 0 is called a non-linear equation because the product such as an . an – 1 appears in the relation. The general first order linear recurrence relation with constant coefficients has the form an + 1 + c an = f(n), n ≥ 0 where c is a constant and f(n) is a function of n when f(n) = 0 for all n  N then the relation is called homogeneous otherwise non-homogeneous relation. Linear homogeneous recurrence relation with constant coefficient: Consider the linear homogeneous recurrence relation with constant coefficients of order two. cnan + cn – 1an – 1 + cn – 2 an – 2 = 0, n ≥ 2 Substitute an = cxn cncxn + cn – 1 cxn – 1 + cn – 2cxn – 2 = 0 With c, x ≠ 0 this becomes cnx2 + cn – 1 x + cn – 2 = 0, it is a quadratic equation also called as characteristic equation. The root x1 and x2 of this equation fall under the following categories. Case 1: If roots are real and distinct then the solution of recurrence relation is an = c1x1n + c2x2n Case 2: If roots are real and equal then the solution of recurrence relation is an = (c1 + n c2) xn CU IDOL SELF LEARNING MATERIAL (SLM)

114 Discrete Mathematical Structures Case 3: If the roots are non repeated and complex say ( + i) and ( – i) then an = c1( + i)n + c2( – i)n Case 4: If the roots are complex and repeated say  ± i and 
i Then an = rn((c1 + n c2)cos n + (c3 + nc4)sin n), r = (2 2 ) Case 1: Roots are real and distinct: Example 7: Solve the recurrence relation an + an – 1 – 6an – 2 = 0, where n ≥ 2, where a0 = – 1, a1 = 8. Solution: The characteristic equation of the recurrence relation is x2 + x – 6 = 0  x2 + 3x – 2x – 6 = 0  x(x + 3) – 2(x + 3) = 0  (x – 2) ( x + 3) = 0  x = 2, – 3 Roots are real and distinct
The solution of recurrence is an = c1x1n + c2x2n … (1) an = c1(2)n + c2(–3)n ... (2) put n = 0 a0 = c1 20 + c2(–3)0  –1 = c1 + c2 Similarly, put n = 1 a1 = c1(2)1 + c2(–3)1  8 = 2 c1 – 3 c2 CU IDOL SELF LEARNING MATERIAL (SLM)

Combinatory 2 115 Solving this system of equations, 1 and 2 we get c1 = 1, c2 = –2. Therefore, an = (2)n – 2 (–3)n Is the general solution of the recurrence relation. Example 8: Solve an = 5an – 1 – 6an – 2 Solution: The characteristic root equation is x2 – 5x + 6 = 0 Hence, the roots are 3 and 2
an = c13n + c22n when initial conditions are not given. Example 9: Solve the recurrence relation 2an + 3 = an + 2 + 2an + 1 – an, where n ≥ 0 where a0 = 1, a1 = 1, a2 = 2 Solution: The characteristic root equation of the relation is 2x3 – x2 – 2x + 1 = 0  (2x – 1) (x – 1) ( x + 1)  roots are ½, 1, – 1 So the solution of recurrence relation is an = c1xn + c2xn + c3xn Substituting the value of roots in the solution we get an = c1 (1/2)n + c2(1)n + c3 (–1)n put n = 0, 1 and 2 CU IDOL SELF LEARNING MATERIAL (SLM)

116 Discrete Mathematical Structures a0 = c1 (1/2)0 + c2(1)0 + c3 (–1)0 ... (1) 0 = c1 + c2 + c3 … (2) a1 = c1 (1/2)1 + c2(1)1 + c3 (–1)1 ... (3) 1 = (1/2) c1 + c2 – c3 a2 = c1 (1/2)2 + c2(1)2 + c3 (–1)2 2 = (1/4) c1 + c2 + c3 Solve 1, 2 and 3 eq. We get c1 = 5/2, c2 = 1/6, c3 = –8/3
an = 5/2 (1/2)n + 1/6(1)n – (8/3)c3 (–1)n Case 2: The roots, x1 & x2 are real and equal: Example 10: Solve an = 4an – 1 – 4an – 2 with initial conditions a0 = 1 a1 = 1. Solution: The characteristic polynomial is x2 – 4x + 4 = 0 x2 – 2x – 2x + 4 = 0  x(x – 2) – 2(x – 2) = 0  (x – 2 ) (x – 2) = 0  x = 2, 2 The general solution of repeated roots is an = (c1 + n c2)xn Substitute the roots an = (c1 + n c2) (2)n CU IDOL SELF LEARNING MATERIAL (SLM)

Combinatory 2 117 Put n = 0 and n = 1 … (1)  a0 = (c1 + 0 c2)(2)0 … (2)  1 = c1  a1 = (c1 + 1c2)(2)1  1 = 2c1 + 2c2 On solving Equation 1 and 2 c1 = 1, c2 = – 1/2 therefore the solution is an = 2n – n 2n – 1 Case 3: The roots are distinct complex conjugate pair: Example 11: Solve the recurrence relation an = 2an – 1 – 2an – 2 where n ≥ 2, a0 = 1, a1 = 2. Solution: The characteristic equation is x2 – 2x + 2 = 0 Roots = (– b ± (b2 4ac) / 2a ) = 2 ± (4 8) / 2 = 1 ± ( 4 / 2) = 1±i An = c1(1 + i)n + c2(1 – i)n We know that 1 + i = 2 (cos (/4) + i sin (π/4) And 1 – i = 2 (cos (– π/4) + i sin (– π/4) an = c1 ( 2 (cos (π/4) + i sin (π/4))n + c2( 2 (cos (– π/4) + i sin (–π/4))n CU IDOL SELF LEARNING MATERIAL (SLM)

118 Discrete Mathematical Structures an = ( 2 )n [c1cos (nπ/4) + i sin (nπ/4) + c2(cos (– nπ/4) – i sin (– nπ/4))]  an = ( 2 )n [(c1 + c2) cos(nπ/4) + (c1 – c2) i sin(nπ/4)] Let c1 + c2 = k1 and (c1 – c2)i = k2 an = ( 2 )n [(k1) cos(nπ/4) + k2i sin(nπ/4) put n = 0, we get k1 = 1 and Put n = 1, we get k2 = 1. Hence the general solution of the equation is an = ( 2 )n (cos(nπ/4 + sin (nπ/4)) Case 4: If the roots are complex and repeated: Example 12: Solve the recurrence relation an + 4 + 8an + 2 + 16an = 0 Solution: The characteristic polynomial is x4 + 8x2 + 16 = 0  (x2 + 4)2 = 0  x = ± 2i, ±2i   = 0 and  = 2 
r = 2 2 = 2 Hence, the solution is an = 2n [(c1 + n c2)cos nπ/2 + (c3 + n c4)sin nπ/2] Where c1 and c2 are constants, if initial conditions are given they are required to be find out. CU IDOL SELF LEARNING MATERIAL (SLM)

Combinatory 2 119 7.4 Non-homogeneous Linear Equations Particular Solutions If anp is the particular solution of the recurrence relation then the total solution is given by an = anh + anp Where anh is the solution of homogenous equation Case 1: If f(n) is constant(an = p). Example 13: Solve an – 4an – 1 + 4an – 2 = 2 with initial conditions a0 = 1a1 = 1 Solution: The general solution of the given recurrence relation an – 4an – 1 + 4an – 2 = 0 is an = 2n – n 2n – 1 Since, f(n) = constant
P – 4P + 4P = 2
P=2
an = 2n – n 2n – 1 + 2 Case 2: If f(n) is in the form cn, c is a constant then (an = P0 + p1n). Example 14: Find the particular solution of the recurrence relation an – 9an – 2 = 3n. Solution: The characteristic equation is x2 – 9 = 0  x2 = 9 x=±3
an = p0 + p1n Then an – 2 = p0 + p1(n – 2) CU IDOL SELF LEARNING MATERIAL (SLM)

120 Discrete Mathematical Structures  an – 9an – 2 = 3n  p0 + p1n – 9(p0 + p1(n – 2)) = 3n  p0 + p1n – 9 p0 – 9p1n + 18p1 = 3n  p0 – 9p0 + 18p1 + n(p1 – 9p1) = 3n Comparing the coefficients We get – 8p0 + 18p1 = 0 and – 8p1 = 3  p0 = – 27/32 and p1 = – 3/8 Therefore, an = p0 + p1n = – 27/32 – n. 3/8 Therefore, total solution is c13n + c2(–3)n + (–27/32 – n. 3/8) Example 15: Solve an – 3an – 1 – 4an – 2 = 4n + 6. Solution: The characteristic polynomial is x2 – 3x – 4 = 0
Roots are – 1 and 4 Since, f(n) is a polynomial of degree one therefore particular solution is an = p0 + p1n  p0 + p1n – 3(p0 + p1(n – 1) ) – 4(p0 + p1(n – 2)) = 4n + 6  p0 + p1n – 3p0 – 3p1n + 3p1 – 4p0 – 4p1n + 8p1 = 4n + 6  p0 – 3p0 + 3p1 – 4p0 + 8p1 + n(p1 – 3p1 – 4p1) = 4n + 6  – 6p0 + 11p1 – 6p1n = 4n + 6  – 6p1 = 4 and – 6p0 + 11p1 = 6 CU IDOL SELF LEARNING MATERIAL (SLM)

Combinatory 2 121  p1 = – 2/3 and – 6 p0 – 11*2/3 = 6  p0 = – 20/9 The total solution is an = c1(–1)n + c2 (4)n – (20/9) – n 2/3 Example 16: Solve an – 3an – 1 – 4a n – 2 = 2n Solution: The characteristic polynomial is x2 – 3x – 4 = 0
Roots are –1 and 4 Since, f(n) = 2n then assume an = P. 2n  (P. 2n) – 3(P. 2n – 1) – 4 (P. 2n – 2) = 2n  [(P 22) – 3 .2 P – 4P ]2n – 2 = 2n  4P – 10 P = 22  – 6P = 4  P = – 2/3 Hence, the solution is an = c1(–1)n + c2(4)n – 2n.2/3 7.5 Generating Function Definition Let a0, a1, a2, … be a sequence of real numbers. The function G(x) = a0 + a1x + a2x2 + … =  a i x i i 0 CU IDOL SELF LEARNING MATERIAL (SLM)

122 Discrete Mathematical Structures Properties 1. 1, 1, 1, 1,1, 0, 0 is G(x) = a0 + a1x + a2x2 + … = 1 + 1x + 1x2 + 1x3 + 1x4 = 4 a i xi i0 2. 1, 2, 1, 0, 0 G(x) = 1 + 2x + x2 = (x + 1)2 3. Generating function for the sequence 1, a, a2, a3, … is G(x) = 1 1 ax 4. G(x) = 1 + x + x2 + x3… = 1 1 x 5. G(x) = 1 – x + x2 – x3… = 1 1 x 6. G(x) = 1 + 2x + 3x2 + 4x3 + … = 1 (1 x)2 7.6 Recurrence Relation by the Method of Generation Functions Example 17: Solve an + 1 – an = 3n, a0 = 1 Solution:      n0 n0 n a n 1x n 1 a n x n 1  0 3  (a1x1 + a2x2 + a3x3 + …) – (a0x + a1x2 + a2x3 + …) = 30 + 31 + 32 + 33 + ….  (a0 + a1x1 + a2x2 + a3x3 + … –a0) – x(a0 + a1x1 + a2x2 + a3x3 + …) = 1 1 3x CU IDOL SELF LEARNING MATERIAL (SLM)

Combinatory 2 123  G(x) – a0 – xG(x) = 1 1 3x  G(x)(1 – x) – 1 = 1 1 3x  G(x)(1 – x) = 1 +1 1 3x  G(x) = 2 3x (1 3x) (1 x) By partial fraction method  G(x) = 3/2 1/ 2 1 3x 1 x  an = 3 3n 1 2 2 Example 18: Solve a n + 2 – 5 an + 1 + 6an = 2, a0 = 3, a1 = 7 Solution:     a n 2 x n 2 5  a n 1x n 2 6  a n x n 2  2 xn 2 n0 n n0 0  (a2x2 + a3x3 + a4x4 + …) – 5(a1x2 + a2x3 + …) + 6(a0x2 + a1x3 + a2x4 + …) = 2x2  x n n 0  (a0 + a1x + a2x2 + a3x3 + a4x4 + … – a0 – a1x) – 5x(a0 + a1x + a2x2 + a3x3 + a4x4 + … – a0) + 6x2(a0 + a1x + a2x2 + a3x3 + a4x4 + …) = 2x2(1 + x + x2 + x3 + …)  (G(x) – a0 – a1x) – 5x(G(x) – a0) + 6x2G(x) = 2x2 1 x CU IDOL SELF LEARNING MATERIAL (SLM)

124 Discrete Mathematical Structures  G(x) – 3 – 7x – 5xG(x) + 15x + 6x2G(x) = 2x2 1 x  G(x)(1 – 5x + 6x2) = 3 – 8x + 2x2 1 x = 3 11x 10x2 1 x  G(x) = 3 11x 10x2 (1 x)(1 5x 6x2 ) = (3 5x) (1 2x) (1 3x) (1 2x) (1 x) = 3 5x (1 3x)(1 x) By partial fraction decomposition = 2 1 1 3x 1 x = 2(3n) + 1 Therefore, an = 2(3n) + 1 Example 19: Solve an – 3an – 1 = n, a0 = 1 Solution:   n1a n x n 3 n1a n 1x n   nx n n 1  (a1x + a2x2 + a3x3 + …) – 3(a0x + a1x2 + a2x3 + …) = x + 2x2 + 3x3 + 4x4 + …  (a0 + a1x + a2x2 + a3x3 + … –a0) – 3x(a0 + a1x + a2x2 + …) = x(1 + 2x + 3x2 + …) CU IDOL SELF LEARNING MATERIAL (SLM)

Combinatory 2 125  (G(x) – a0) – 3x G(x) = x 1 (1 x)2  G(x) – 1 – 3x G(x) = x (1 x)2  G(x)(1 – 3x) = 1 + x (1 x)2  G(x) = 1x (1 3x) (1 3x) (1 x)2 Using a partial fraction x AB C (1 3x) (1 x)2  (1 x) (1 x)2 (1 3x) or x = A (1 – x)(1 – 3x) + B(1 – 3x) + C(1 – x)2 On Solving, we get A = – 1/4 B = – 1/2 C=¾ Therefore, f(x) = (1 x  14  12 3/4 3x) (1 x) (1 x)2 (1 3x) = 7/4  14  12 (1 3x) (1 x) (1 x)2 = 7/4(3n) – (1/4)n – (1/2)(n + 1) = 7/4(3n) – (1/2)n – (3/4). CU IDOL SELF LEARNING MATERIAL (SLM)

126 Discrete Mathematical Structures 7.7 Solution of Combinatorial Problem using G.F. Problem 1: How many positive factors does the number N = 235473115 have? Solution: From the Unique Factorization Theorem for integers, A divides N = pk1 . . . pks (pi’s are distinct primes) iff A = pl1 . . . pls , with 0 ≤ li ≤ ki, i = 1, . . . , s. By the product rule, there are (k1 + 1) (k2 + 1) . . . (ks + 1) choices for A, since li’s can be chosen independently in ki + 1 ways each. In our case, the number of positive factors is 4 • 5 • 4 • 6 = 480. Problem 2: Let n 1 circles be drawn on the plane. What is the greatest number of parts (bounded or unbounded) can they divide the plane? Solution: If an is the number, then it is easy to show (similarly to 3(i)) that an ≤ an − 1 + 2(n − 1), n ≥ 2, a1 = 2. This leads to an = n2 − n + 2, n ≥ 1. Remark. Using argument similar to the one in Problem 3(ii), one can show that in R3, n spheres can divide the space in at most n(n2 − 3n + 8)/3 parts. Again, the existence of such n circles or spheres for every n can be easily proven by induction on n or by an explicit construction. It seems that the generalization for n spheres in Rm is similar to the one in Problem 3(iii). Can we get a nice expression in this case? Problem 3: Consider a tournament which starts with n 1 teams. In the first round, all teams are divided into pairs if n is even, and the winner in each pair passes to the next round (no ties). If n is odd, then one random (lucky) team passes to the next round without playing. The second round CU IDOL SELF LEARNING MATERIAL (SLM)

Combinatory 2 127 proceeds similarly. At the end, only one team is left – the winner. Find a simple formula for the total number of games played in the tournament. Solution 1: The number of games played is equal to the number of teams which lost their game: every team but the winner loses exactly one game and the every game eliminates exactly one team. Therefore, the number of games in the tournament is n 1. Solution 2: Let f(n), n1, denotes the number of all games played. Assume f(1) = 0. Working out examples for small n (or for n = 2k), we come to a conjecture f(n) = n − 1. We can prove it by induction. Suppose it is established for all m, 1 ≤ m < n. Then, if n = 2k, we have f(n) = f(k) + k = (k − 1) + k = 2k − 1 = n − 1. If n = 2k + 1, we have f(n) = f(k + 1) + k = k + k = 2k = n − 1. Thus, the statement is proven. 7.8 Summary
A recurrence relation is a functional relation between the independent variable x, dependent variable f(x) and the differences of various order of f(x). A recurrence relation is also called a difference equation, and we will use these two terms interchangeably.
A linear homogeneous recurrence relation of degree k with constant coefficients is a recurrence relation of the form an = c1an − 1 + c2an − 2 + . . . + ckan−k, where c1, c2, . . . , ck  R and ck 6 = 0. Linear refers to the fact that an − 1, an−2, . . . , an−k appear in separate terms and to the first power. Homogeneous refers to the fact that the total degree of each term is the same (thus there is no constant term). CU IDOL SELF LEARNING MATERIAL (SLM)

128 Discrete Mathematical Structures
Generating function is a method to solve the recurrence relations. Let us consider, the sequence a0, a1, a2 .... ar of real numbers. For some interval of real numbers containing zero values at t is given, the function G(t) is defined by the series: G(t) = a0, a1t + a2 t2 + ... + ar tr + ... equation (i)
This function G(t) is called the generating function of the sequence ar. 7.9 Key Words/Abbreviations
Homogeneous: The total degree of each term of equation is the same.
Non-homogeneous: The total degree of each term of equation is the different.
Recurrence Relation: A relation which can be obtained by using its previous terms with specifying initial condition.
Generating Function: A way of encoding an infinite sequence of numbers (an) by treating them as the coefficients of a power series. 7.10 Learning Activity 1. State difference between Homogeneous and Non-homogeneous recurrence relations. ----------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------- 2. What is the solution of recurrence relation: (i) If roots are real and distinct. (ii) If roots are real and equal. (iii) If the roots are non-repeated and complex. (iv) If the roots are complex and repeated. ----------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------- CU IDOL SELF LEARNING MATERIAL (SLM)

Combinatory 2 129 7.11 Unit End Questions (MCQ and Descriptive) A. Descriptive Types Questions 1. Find the first five terms of the sequence defined by the recurrence relation. (a) an = 3an – 1 n ≥ 2, a1 = 1 (b) an = 2an – 1 + n n ≥ 2, a1 = 1 (c) bn = n(bn – 1)2 n ≥ 1, b0 = 1 (d) an = nan – 1 + n2an – 2 n ≥ 2, a0 = 1, a1 = 1. 2. Use Iterative or backtracking method an = – 2an – 1, n ≥ 1 3. Find the solution of the followings: (a) an = an – 1 + 2, a0 = 1 (b) bn = nbn – 1, b0 = 5 4. Use characteristic root method to solve the given recurrence relation (a) an = an – 1 + 6an – 1, n ≥ 2, a0 = 1, a1 = 1 (b) bn = bn – 1 + 2bn – 2 b0 = 2, b1 = 7 5. Use characteristic root method to solve the given non-homogenous recurrence relation (a) bn – 5bn – 1 + 6bn – 2 = 1 (b) bn + 2 – 5bn + 1 + 6bn = n2 (c) an = 5an – 1 – 6an – 2 + 7n 6. Use generating function to solve the given recurrence relations (a) an = 3an – 1 + 4, a0 = 5 (b) bn – 7bn – 1 + 10bn – 2 = 0, b0 = 3, b1 = 3 Answers: (b) 1, 4, 11, 26 1. (a) 1, 3, 9, 27, 51 (d) 1, 1, 6, 27 (c) 1, 1, 2, 12 CU IDOL SELF LEARNING MATERIAL (SLM)

130 Discrete Mathematical Structures 2. an = 3(–2)n (b) 5 n! 3. (a) 1 + 2n (b) bn = 3.2n – ( – 1)n 4. (a) an = 3n (b) bn = c1 2n + c2 3n + (1/2) n2 + (3n/2) + 5/2 5. (a) bn = c1 3n + c22n + 1/2 (b) bn = 13(5)n – 10(2)n (c) an = c1 3n + c2 2n + (49/20)7n 6. (a) an = 7. 3n – 2 B. Multiple Choice/Objective Type Questions 1. Find the fourth term of the sequence an = an – 12. (a) 250 (b) 250 (c) 200 (d) 100 2. A relation which can be obtained by using its previous terms with specifying initial conditions is called __________. (a) relation (b) recurrence relation (c) sequence (d) none of these 3. The Second term of Sequence of an = n + 2 is __________. (a) 2 (b) 4 (c) 6 (d) 8 4. The nth term of the sequence an = {2, 4, 6, 8……..} is __________. (a) n (b) 2n (c) 3n (d) 4n 5. The degree of the given recurrence relation an = an – 1 + an – 5 is ______ . (a) 2 (b) 4 (c) 5 (d) 6 Answers 1. (a), 2. (b), 3. (b), 4. (b), 5. (c) CU IDOL SELF LEARNING MATERIAL (SLM)

Combinatory 2 131 7.12 References References Books: 1. http://home.iitk.ac.in/~arlal/book/mth202.pdf 2. http://www.cs.yale.edu/homes/aspnes/classes/202/notes.pdf Web Resources: 1. https://www.geeksforgeeks.org/discrete – maths – generating – functions – introduction – prerequisites/ 2. https://www.geeksforgeeks.org/discrete – mathematics – types – of – recurrence – relations – set – 2/ 3. https://www.javatpoint.com/recurrence – relations CU IDOL SELF LEARNING MATERIAL (SLM)

UNIT 8 GRAPHS Structure: 8.0 Learning Objectives 8.1 Introduction 8.2 Graph Definition 8.3 Types of Graph Connected Graphs 8.4 Components of Graph 8.5 Euler and Hamilton Paths 8.6 Graph Coloring 8.7 Chromatic Number of a Graph 8.8 Summary of the Unit 8.9 Key Words/Abbreviations 8.10 Learning Activity 8.11 Unit End Questions (MCQ and Descriptive) 8.12 References 8.0 Learning Objectives After studying this unit, you will be able to:
Define Graph Terminology.
Describe Different Types of Graph, Connected Graphs.

Graphs 133
Explain Euler Graph, Hamiltonian Path and Circuits.
Graph Colorings.
Chromatic Number. 8.1 Introduction Graph Theory is a relatively new area of mathematics, first studied by the super famous mathematician Leonhard Euler in 1735. Since then it has blossomed in to a powerful tool used in nearly every branch of science and is currently an active area of mathematics research. The chromatic number of a graph G is the smallest number of colors needed to color the vertices of G so that no two adjacent vertices share the same color (Skiena 1990, p. 210), i.e., the smallest value of k possible to obtain a k-coloring. Minimal colorings and chromatic numbers for a sample of graphs are illustrated above. The chromatic number of a graph G is most commonly denoted
(G) (e.g., Skiena 1990, West 2000, Godsil and Royle 2001, Pemmaraju and Skiena 2003), but occasionally also (G). Empty graphs have chromatic number 1, while non-empty bipartite graphs have chromatic number 2. 8.2 Graph Definition A Graph is collection of vertices and edges where each edge is assigned to a pair of vertices. A graph is an ordered pair (V, E) of two sets V and E, where V is the non-empty set of vertices and E is the set of edges such that each element of E is assigned with unique unordered pair v1, v2 of elements of V. A Graph is denoted by G. CU IDOL SELF LEARNING MATERIAL (SLM)

134 Discrete Mathematical Structures e.g. v1 e1 v2 e2 e3 e6 v3 e4 v5 e5 v4 (G) In the above graph G, the vertices and edges sets are as follows: V = {v1, v2, v3, v4, v5} E = {e1, e2, e3, e4, e5, e6} 8.3 Types of Graph Connected Graphs There are different types of graph, which are listed below: (i) Simple graph: A graph in which each edge connects two different vertices and where no two edges connect the same pair of vertices is called a simple graph. For example, Consider the following graph – The above graph is a simple graph, since no vertex has a self-loop and no two vertices have more than one edge connecting them. CU IDOL SELF LEARNING MATERIAL (SLM)

Graphs 135 (ii) Multigraph: A graph in which multiple edges may connect the same pair of vertices is called a multigraph. Since, there can be multiple edges between the same pair of vertices, the multiplicity of edge tells the number of edges between two vertices. E B C D A F (iii) Null graph: Also called an empty graph, a null graph is a graph in which there are no edges between any of its vertices. a bc (iv) Connected graph: A graph in which there is a path of edges between every pair of vertices in the graph. Mary's graph is a connected graph, since there is a way to get from every city on the map to every other city. ac bd CU IDOL SELF LEARNING MATERIAL (SLM)

136 Discrete Mathematical Structures (v) Disconnected graph: A graph in which the path of edges does not always connect every vertex. ac bd (vi) Bipartite graph: A graph that can be split into two sets of vertices such that edges only go between sets, not within them. ac bd (vii) Weighted graph: A graph in which weights, or numerical values, are assigned to each of the edges. Mary's graph is a weighted graph, where the distances between the cities are the weights of the edges. 11 2 3 42 07 3 8 43 CU IDOL SELF LEARNING MATERIAL (SLM)

Graphs 137 (viii) Directed graph: A graph in which the edges are directed by arrows, indicating that the relationship, represented by the edge, only applies from one vertex to the other, but not the other way around. In other words, if a directed edge has an arrow from A to B, A is related to B, but B is not related to A. ac b (ix) Undirected graph: A graph whose edges are not directed. Mary's graph is an undirected graph, because the routes between cities go both ways. ac b (x) Planar graph: A graph that can be drawn so that all of the edges of the graph do not cross each other. ac bd CU IDOL SELF LEARNING MATERIAL (SLM)

138 Discrete Mathematical Structures (xi) Nonplanar graph: A graph that is not a planar graph. In other words, a graph that cannot be drawn without at least one pair of its edges crossing. K5 These graphs cannot be drawn in a plane so that no edges cross hence they are non-planar graphs. Note: Diagrams are added from point (iii) to point (ix) 8.4 Components of Graph v1 e1 v2 In the above discussion some terms regarding graphs have already been explained such as vertices, e3 e2 edges, directed and undirected edges etc. There are more terms which describe properties of vertices and edges. v3 (G) 1. Adjacency If there is an edge between two vertices v1 and v2 then they are called as adjacent to each other. Here v1 and v2 are adjacent vertices. Similarly, (v2, v3) and (v3, v1) also adjacent vertices. 2. Incidence If an edge starts (or ends) from a vertex then the edge is called as incident edge on the vertex. CU IDOL SELF LEARNING MATERIAL (SLM)

Graphs 139 Example: e1 v2 v1 e2 e4 v4 e3 v3 v2 Here edge e1 is incident on v1 and v2 edge e2 is incident on v2 and v3 edge e3 is incident on v3 and v4 edge e4 is incident on v4 and v1 Example: v1 e1 e3 e2 e4 v3 Here e1 is incident on v1 and v2 e2 is incident on v2 and v3 e3 and e4 are incident on v1 and v3. Note: e3 and e4 have same end vertices hence we can call them parallel edges. 3. Degree of Vertex The number of edges incident (coming or leaving but counted once only) on a vertex is called the ‘degree’ or the ‘valency’ of the vertex. CU IDOL SELF LEARNING MATERIAL (SLM)

140 Discrete Mathematical Structures It is denoted by d(V) Indegree of a Graph: Indegree of vertex V is the number of edges which are coming into the vertex V. Outdegree of a Graph: Outdegree of vertex V is the number of edges which are going out from the vertex V. A vertex with degree one is called as pendent vertex. A vertex with degree zero is called as isolated vertex. If an edge having same end vertices then the edge is called loop. The degree of loop is 2. e1 v2 d(v1) = 5 v1 e2 e3 d(v2) = 3 d(v3) = 5 v5 e9 d(v4) = 4 e6 e7 v7 e8 e10 v3 d(v5) = 4 d(v6) = 1 v6 v4 e5 d(v7) = 0 e4 Here v6 is a pendent vertex and v7 is an isolated vertex. 4. Degree of Graph The sum of the degrees of all the vertices of the same graph called degree of the graph. Degree of graph is denoted by d(G) v1 v2 d(v1) = 2 d(v2) = 2 d(v3) = 4 v4 v3 d(v4) = 2 CU IDOL SELF LEARNING MATERIAL (SLM)

Graphs 141  d(G) = 2 + 2 + 4 + 2 d(G) = 10 8.5 Euler and Hamilton Paths Euler’s Graph: A connected graph G is called an Euler graph, if there is a closed trail which includes every edge of the graph G. An Euler path is a path that uses every edge of a graph exactly once. An Euler path starts and ends at different vertices. An Euler circuit is a circuit that uses every edge of a graph exactly once. An Euler circuit always starts and ends at the same vertex. A connected graph G is an Euler graph if and only if all vertices of G are of even degree, and a connected graph G is Eulerian if and only if its edge set can be decomposed into cycles. a1b d 72 3 4 f 6 c 5e The above graph is an Euler graph as “a1b2c3d4e5c6f7g” covers all the edges of the graph. Note: Above diagram is added now. Theorem 1 A connected multigraph with at least two vertices has an Euler circuit if and only if each of its vertices has an even degree. Theorem 2 A connected multigraph has an Euler path but not an Euler circuit if and only if it has exactly two vertices of odd degree. CU IDOL SELF LEARNING MATERIAL (SLM)

142 Discrete Mathematical Structures Algorithm for Constructing an Euler Circuit Algorithm Euler Circuit (G : connected multigraph with all vertices of even degree) 1: circuit = a circuit in G beginning at an arbitrarily chosen vertex with edges successively added to form a path that returns to this vertex 2: H = G with the edges of this circuit and all isolated vertices removed 3: while H has edges, do the following: 4: subcircuit = a circuit in H beginning at a vertex in G that also is an endpoint of an edge of circuit 5: H = H with edges of subcircuit and all isolated vertices removed 6: circuit = circuit with subcircuit inserted at the appropriate vertex 7: end while 8: return circuit {circuit is an Euler circuit} 9: That circuit is an Euler circuit Example 1: Determine whether the given graph has an Euler circuit. Construct such a circuit when one exists. If no Euler circuit exists, determine whether the graph has an Euler path and construct such a path if one exists. bc aed By theorem 1, we know this graph does not have an Euler circuit because we have four vertices of odd degree. By theorem 2, we know this graph does not have an Euler path because we have four vertices of odd degree. CU IDOL SELF LEARNING MATERIAL (SLM)