Graph Theory and Combinatorics — Summer 2022

07 (1) Let m be the number of odd degree vertices of a graph. Which of the following options are always true? (A) m is odd (B) m is a multiple of 4 (C) m is even (D) m is prime (2) Asimple graph with n vertices can have at most ---- edges. (A) n (B) n(n−1) (C) n(n+1) (D) n222 (3) Any two vertices of a tree are connected with --- path(s) (A) exactly one (B) two different (C) no (D) many (4) In a connected graph Ga sub-graph Hof Gthat includes all the vertices of Gand is also a tree is known as ---- (A) surrounding tree (B) super tree (C) special tree (D) spanning tree (5) Lily is trying to decide what to wear. She has shirts in the following colors: red, purple, and blue, and she has pants in the following colors: black and white. How many different outfits can Lily choose from (assuming she selects one shirt and one pair of pants)? (A) 6 (B) 5 (C) 12 (D) (6) In a survey of 1000 consumers it is found that 720 consumers likes product Aand 450 liked product B. What is the least number that must have liked both the products? (A) 70 (B) 170 (C) 270 (D) 1720 (7) The number of words, with or without meaning, that can be formed with the letters of the word ‘CHAIR’ are --- (A) 20 (B) 40 (C) 120 (D)

07 Answer the following questions for the given graph: (1) How many edges are incident on vertex v ?4 (2) Name the parallel edges in the graph. (3) Name the edge which is a self-loop. (4) Name the pendant vertex. (5) Verify the statement (in the graph given) “ the sum of degrees of all vertices in a graph is twice the number of edges in the graph”.

List five situations from everyday life in which graphs arise naturally and describe one of them.

(1) Check whether the below two graphs are isomorphic or not. (A) (B) (2) For the graph (A) above form two sets Pand Qof vertices where one end of the edge is in the set Pand other end of the edge is in the set Q. Write the name of such a graph.

Prove the following: (1) In any graph the sum of degrees of all vertices is twice the number of edges in the graph (2) In any graph, the number of vertices with odd degree is even.

Obtain the incidence matrix and adjacency matrix of the following graph.

(1) How many integers from 1 to 100 are multiples of 2 or 3? (2) For the following graph draw the graph

G −{v ,v } (ii) G −{e ,e ,e }

 Acomplete bipartite graph is a simple bipartite graph with bipartition (X, Y) in which each vertex of Xis joined to each vertex of Y; if |X|= m and |Y| = n, such a graph is denoted by Km,n. (1) Draw the graph K . 3,3  Awalk in Gis a finite non-null sequence W – v e v e v …e v 0 1 1 2 2 k k whose terms are alternately vertices and edges, such that, for 1 ≤ i ≤ k, the ends of e are v and v . i i−1 i  If the edges of a walk are distinct then it is called a trail.  If the vertices of a walk are distinct then it is called a path. (2) Obtain a walk, trail and a path of the graph given.

(1) Draw a connected graph. Also draw a disconnected graph having three components. (2) In the graph of Que 3 (a) (2) obtain a closed walk and a cycle.03

(1) Draw a tree having four vertices (2) Given a connected graph G, a spanning tree of Gis a subgraph of Gwhich is a tree and includes all the vertices of G. Draw a spanning tree for the following graph01 (3) Does the following graph a tree? G=(V,E) with V={a,b,c,d,e} and E={{a,b},{a,e},{b,c},{c,d},{d,e}. (4) For the following tree if we designate vertex f as a root then mention the children of f.

 The unique solution of the recurrence relation a = da where n+1 n n ≥ 0, d is a constant and is given by a = a dn, n ≥ 0. n 0 (1) Find the unique solution of the recurrence relation a = 7a , n n−1 where n ≥ 1 and a = 98.2 (2) Abank pays 6% annual interest on savings, compounding the interest monthly. If Vishal deposits ₹ 10,000 on the first day of May, how much this deposit be worth a year later?

Prove the following: 1. If in a graph Gthere is one and only one path between every pair of vertices than graph Gis a tree. 2. Atree with n vertices has (n-1) edges. 3. Any connected graph Gwith n vertices and (n-1) edges is a tree. 4. Agraph with n vertices, (n-1) edges and no circuit is a connected graph.

1. Acollege library has 40 textbooks on Sociology and 50 textbooks dealing with Anthropology. In how many ways a student of this college can select textbooks in order to learn more about one or the other of these two subjects? 2. The drama club of Central University is holding tryouts for a spring play. With six men and eight women auditioning for the leading male and female roles. In how many ways director can cast his leading couple? 3. In how many ways the manufacture of license plates consisting of two letters followed by four digits (i) if no letter or digit repeated (ii) with repetition of letters and digits (iii) letters only vowel and digits even numbers only with repetition. 4. How many outcomes are possible when three dice are rolled, if no two of them may be the same? 5. Six people are to sit at a round table; how many seating arrangements are there? 6. How many ways are there to line up six people so that a particular pair of people is not adjacent? 7. How many permutations are there of the letters in Mississippi?

 The number of solutions to ∑n x = k is (k+n−1), x ≥ i=1 i k i03 1. Find the number of solutions to x +x +x +x = 20 with x ≥ 0, x ≥ 1, x ≥ 2 and x ≥ −1.234  Second order linear homogeneous recurrence relation is c a +c a +c a = 0,n ≥ 0,c ,c ,c are real n n n−1 n−1 n−2 n−2 n n−1 n−2 constants and c ≠ 0. Solution to this is in the form a = ckn where n n c,k ≠ 0 where k satisfies quadratic equation c k2 +c k+ n n−1 c = 0. If two roots k ,k of equation are real and distinct then n−2 1 we take a = Ak n +Bk nas general solution where Aand Bare n 1 arbitrary constants.04 2. Solve the recurrence relation a +a −6a = 0 for n ≥ n n−1 n−2 given that a = −1,a = 8.01

 Derangements: Nothing is in its right place. Number of derangements of n objects is d = n!(1−1+ 1 − 1 + 1 − 1 +⋯(−1)n 1 ). For n ≥ 7 a very n 2! 3! 4! 5! n! good approximation of (1−1+ 1 − 1 + 1 − 1 +⋯(−1)n 1 ) ≈ 1 = 0.36786 2! 3! 4! 5! n! e 1. Obtain the derangements of numbers 1,2,3,…,10 2. Prove that the derangements of numbers 1, 2, 3, 4 are 9 and list them.