Graph Theory and Combinatorics — Winter 2023

Check given two graphs are isomorphic or not. Justify your answer.

Prove that the number of vertices of odd degree in a graph is always even. Also, take any graph and verify it.

1) Define Spanning Tree. 2) In any tree (with two or more vertices), there are at least _______ pendant vertices. 3) If a given tree be a complete 3-ary tree with 25 leaves then what is the height of a tree? 4) Let Land Lbe two sorted lists of ascending numbers, where Lcontains121 elements and Lcontains 6 elements. Then Land Lcan be merged into one212 ascending list Lthan at most how many comparisons are required. 5) Does the given 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}}. 6) Acode for {a, b, c, d, e} is given by a:00, b:01, c:101, d:x10, e:yz1, where x, y, z ∈ {0, 1}. Determine x, y and z so that the given code is a prefix code. 7) Let T = (V, E) be a binary tree. In Fig, we find the subtree of Trooted at vertex p. (The dashed line coming into vertex p indicates that there is more to the tree Tthan what appears in the figure.) If the level number for vertex u is 37, what are the level numbers for vertices p, s , t , x, y, and z?1

For the network shown in fig. let the capacity of each edge be 10. If each edge e in the figure is labeled by a function f, as shown, determine the values of s, t, w, x and y so that f is a flow in the network. Also find the value of this flow.

Find Dual Graph For the given Graph G.

1) Describe Königsberg bridge problem. 2) Following graph Contains a Hamilton path or Hamilton Cycle? Justify your answer.

Find Max flow min cut value for a given graph.

1) In a graph the total number of edges are 87 than the sum of degrees of all vertices is _____________. 2) What is the chromatic Number for Petersen graph ? 3) If Graph G(V,E) is a Complete Graphs then Chromatic Polynomials P(G, λ) = _____________.

Five Faculties Rajesh, Divy, Shivam, Brijesh and Paresh are members of three sports games, Cricket, Football and wallyball. Each game is to select a Faculty representative for2 manage game properly. Can a selection be made in such a way that each game has a distinct representative? For solving this problem construct a transport network.

Determine which of the graph in give figure are planar. If a graph is planar, redraw it with no edges overlapping. If it is non planar, find a subgraph homeomorphic to either Kor5 K 3,3.

Aclassroom contains 25 microcomputers that must be connected to a wall socket that has four outlets. Connections are made by using extension cords that have four outlets each. What is the least number of cords needed to get these computers set up for class use?

For given preference of men and women find the solution for stable marriage problem.

Using proper method to find at least 3 De Bruijn Sequence B(k,n) for Input n = 2, k = (Base).

Ms Pezzulo teaches geometry and then biology to a class of 12 advanced students in a classroom that has only 12 desks. In how many ways can she assign the students to these desks so that

no student is seated at the same desk for both classes?

there are exactly six students each of whom occupies the same desk for both classes?

Determine the number of positive integers n, 1 ≤ n ≤ 2000 that are 1) not divisible by 2, 3 or 2) not divisible by 2, 3, 5 or 3) not divisible by 2, 3 or 5 but are divisible by

1) The MASSASAUGA is a brown and white venomous snake indigenous to North America. Arranging all of the letters in MASSASAUGA, we find that there are how many possible arrangements.3 2) Astudent taking a history examination is directed to answer the seven of 10 essay questions. If the student must answer three questions from the first five and four questions from the last five, so How many ways the student can answer the examination? 3) Amessage is made up of 15 different symbols and is to be transmitted through a communication channel. In addition to the 15 symbols, the transmitter will also send a total of 60 (blank) spaces between the symbols, with at least three spaces between each pair of consecutive symbols. In how many ways can the transmitter send such a message?

Determine the generating function for the sequence a , a , a ...., where a is the number of o 1 2 n partitions of the nonnegative integer n into (a) even summands; (b) distinct even summands; (c) distinct odd summands.

In how many ways can two dozen identical robots be assigned to four assembly lines with

at least three robots assigned to each line? (b) at least three, but no more than nine, robots assigned to each line?

Define Homogeneous and non-Homogeneous Recurrence Relation. Find the unique solution of the recurrence relation a −3a = 5(7n), where n ≥ 1 and a = 2. n n−1 0

The number of bacteria in a culture is 1000 (approximately), and this number increases 250% every two hours. Use a recurrence relation to determine the number of bacteria present after one day.

Solve the recurrence relation a +a −6a = 0, where n ≥ 2 and a = −1, a = n n−1 n−2 0 1