| Website for students | VTU NOTES
USNCS 42
Session: Jan’08 to June’08
Graph Theory and Combinatorics Test - 1
Class : 4th Sem CS ‘A’, ‘B’Duration : 90 minutes
Faculty: NNHMax. marks: 50
Note: All questions carry equal marks. Answer 5 questions, choosing at least 2 questions from each part.
PART - A
1. a) Define the complement of a graph with an example. When do we call a graph self-complementary?
b)Can there exist a graph which is (i) a complete graph but not regular? (ii) complete bipartite
and also regular? (iii) a complete graph and also bipartite? Explain.
2. a)Prove that in a hypercube Qn, the number of edges is n.2n-1. Hence determine the number of edges in Q8.
b)Define a bipartite graph and a complete bipartite graph. Verify whether the graph G1 is complete bipartite.
G1 G2 G3 G4
3. a) Define isomorphism of graphs. Give an example to show that two graphs need not be isomorphic
though they have an equal number of edges, equal number of vertices and equal number of vertices
with a given degree.
b) Verify whether the graphs G2 and G3given above are isomorphic. Give reasons for your answer.
4 a) State and prove the necessary and sufficient condition for an undirected graph to have an Euler circuit.
b) Find an Euler circuit for the graph G4 given above.
PART - B
5. a) A man, a woman, a boy, a girl and a dog are walking down a long and winding road one after the other.
(i) In how many ways can this happen if the dog immediately follows the boy? (ii) In how many ways
can this happen if the dog is between the man and boy and nobody else?
b)Find the number of ways that 5 men and 5 women sit around a table, if
(i) there is no restriction. (ii) no two women sit together.
6. a)How many ways are there to select a committee to develop a course at a school if the committee is to
consist of 3 faculty members from the mathematics department and 4 from the computer science
department, if there are 9 faculty members in the mathematics department and 11 in the computer
science department?
b)State the Binomial theorem for two variables ‘x’ and ‘y’. Provide a combinatorial proof for the same.
Hence or otherwise, prove that .
7. a)Determine the co-efficient of w5z3 in the expansion of (w+ z)8. Also, determine the sum
of allthe co-efficients in the above expansion.
b) A total of Rs.10000 is to be distributed to four persons A, B, C, D in multiples of Rs.1000. In how
many ways can the distribution be done if (i) there is no restriction (ii) everyone receives at least
Rs.1000?
8. Consider drawing ‘n’ semicircles on and above a horizontal line, with no two semicircles intersecting.
(Two such drawings involving two semicircles are as shown below)
a) (i) How many different drawings are there for two semicircles?
(ii) How many different drawings are there for three semicircles?
b) Generalize the result of a) for‘n’ semicircles.
*******************************************
CS 42
Graph Theory and Combinatorics Test – 1
Scheme of Valuation
Class : 4th Sem CS ‘A’, ‘B’Duration : 90 minutes
Faculty: NNHMax. marks : 50
PART - A
1. a) Consider a graph G = (V, E) with n vertices. The complement of G is a graph containing all the vertices of G
and all those edges of Kn which are not in G. ------2 marks
A graph G is said to be self complementary if G is isomorphic to its complement. ------1 mark
Ex:
------2 marks.
b) (i) No. Because every complete graph Knis (n-1) regular. ------1 mark
(ii) Yes. Every complete bipartite graph Kn,n is n regular. ------2 marks
(iii) Yes. The complete graph K2 is also bipartite. ------2 marks.
2. a) The number of vertices in Qn is 2n, each of degree n. ------2 marks
Thus, by handshaking lemma, the number of edges in the hypercube Qn is given by n.2n-1. ---- 2 marks
Accordingly, the number of edges in Q8 is given by 1024. ------1 mark.
b) A graph G = (V, E) is said to be bipartite if V can be partitioned into disjoint subsets V1 and V2 such that
every edge of G is incident with a vertex of V1 and a vertex of V2. ------1 mark
A graph G = (V, E) is said to be complete bipartite if G is bipartite with V = V1 U V2 such that every vertex in
V1 is adjacent to every vertex of V2. ------2 marks
The vertex set of the given graph can be partitioned into V1 = {a, c, e} and V2 = {b, d, f}. But the vertex ‘c’ is
not adjacent to ‘f’. Also, the vertex ‘e’ is not adjacent to ‘b’. Thus, the given graph is bipartite but not
complete bipartite. ------2 marks.
3. a) Let G1 = (V1, E1) and G2 = (V2, E2) be two undirected graphs. A function f : V1 V2 is called a graph
isomorphism if (i) f is one-one and onto and (ii) For all a, b є V1, {a, b}є E1 if and only if {f(a), f(b)}є E2.
------3 marks
Example of two non-isomorphic graphs having an equal number of edges, equal number of vertices with a
given degree:
------2 marks.
b) We define a function F : V1 V2 as follows.
F(a) = p, F(b) = s, F(c) = t, F(d) = q, F(e) = r, F(f) = v, F(g) = u, F(h) = w, F(i) = x, F(j) = y. --- 2 marks
We can see that this function is one-one and onto and is defined in such a way that it preserves
adjacency of vertices. Thus, the given two graphs are isomorphic. ------3 marks.
4 a) Statement ------1 mark
Proof of the necessary condition ------2 marks
Proof of the sufficiency condition ------2 marks.
b) The given graph is connected and the degree of every vertex is even. Thus, the graph contains an Euler circuit.
We construct the Euler circuit as follows. ------1 mark
We can obtain a circuit at the vertex ‘a’ given by a-b-c-g-k-j-i-h-d-a. Now, deleting all the edges and the
resultant isolated vertices in this circuit, we get a subgraph of the given graph as follows.
------2 marks
This subgraph has an Euler circuit given by b-g-j-f-b-e-i-f-e-d-b.
Thus, combining this Euler circuit with the circuit that we have considered, we have
a-b-g-j-f-b-e-i-f-e-d-b-c-g-k-j-i-h-d-a which is the required Euler circuit for the graph. ------2 marks.
PART – B
5. a) A man, a woman, a boy, a girl and a dog are walking down a long and winding road one after the other.
(i) Since the dog immediately follows the boy, the dog has no choice of position. Thus, this can be done in
4! = 24 ways. ------2 marks
(ii) Here, the position of the dog is fixed between the man and the boy. Also, either the man is before the dog
and the boy after the dog or the boy is before the dog and the man behind it. This can be done in 2! ways.
Thus, the total number of ways is given by 2! X 3! = 12 ways. ------3 marks.
b) Find the number of ways that 5 men and 5 women sit around a table, if
(i) Fixing the position of 1 person (male/female), we can see that the number of linear arrangements of the
other 9 people can be made in 9! ways. Thus, the number of circular arrangements without any restriction is
given by 9!. ------2 marks
(ii) Since no two women can sit together, they have to be arranged in such a way that they sit alternatingly with
the 5 men which can be arranged in 4! ways. Thus, the women can be arranged in 5! ways so that the
number of arrangements with the given restriction is given by 4! X 5! . ------3 marks.
6. a) Selecting 3 from 9 faculty members in the Mathematics department can be done in C(9, 3) ways. --- 2 marks
Selecting 4 from 11 faculty members in the Computer Science department can be done in C(11, 4) ways.
------2 marks
Thus, by the rule of product, the number of ways of selecting 3 out of 9 Mathematics faculty and 4 out of
11 Computer Science faculty can be done in C(9, 3) X C(11, 4) ways. ------1 mark.
b) Statement ------1 mark
Proof ------3 marks
In the result, taking x = y = 1, we get the result . ------1 mark.
7. a) The co-efficient of in the expansion of (x + y)n is given by C(n, r). ------1 mark
Thus, the co-efficient of w5z3 in the expansion of (w+ z)8 is given by C(8, 5) = 56. ------2 marks
The sum of the all the co-efficients in the expansion of (x + y)nis given by . ---- 1 mark
Thus, the sum of all the co-efficients in the expansion of (w+ z)8 is given by 28 = 256. ------1 mark.
b) Let 1000 x denote the amount given to the person A, Let 1000 y denote the amount given to the person B,
Let 1000 z denote the amount given to the person C and let 1000 w denote the amount given to the person D.
(i) We can represent the above situation mathematically as
1000 x + 1000 y + 1000 z + 1000 w = 10000 given that x, y, z, w ≥ 0.
(or) x + y + z + w = 10 given that x, y, z, w ≥ 0. ------1 mark
The number of integer solutions for the above equation is given by C(4 + 10 – 1, 10) = C(13, 10) ways.
Thus, without any restriction, the amount can be distributed in C(13, 10)ways. ------1 mark
(ii) Given that everyone receives atleast Rs. 1000, the problem can be reframed as
1000 x + 1000 y + 1000 z + 1000 w = 10000 given that x, y, z, w ≥ 1. ------1 mark
(or) x + y + z + w = 10 given that x, y, z, w ≥ 1.
Taking x1 = x –1, y1 = y – 1, z1 = z – 1 and w1 = w – 1, we have the problem rewritten as
x1 + y1 + z1 + w1 = 6 given that x1, y1, z1, w1 ≥ 0. ------1 mark
This equation has C(4 + 6 – 1, 6) = C(9, 6) positive integral solutions. Thus, keeping the above
restriction, we can see that the given equation also has C(9, 6) solutions. ------1 mark.
8. a) (i) There are 2 different drawings for two semicircles as shown below.
------2 marks
(ii) There are 5 different drawings for three semicircles as shown below.
------3 marks.
b) From the above result, we can see that the number of ways of drawing 2 semicircles is given by b2 and the
number of ways of drawing 3 semicircles is given by b3. ------1 mark
We can see that the ways in which we draw ‘n’ semicircles is the same as the number of ways of
arranging ‘n’ 0’s and ‘n’ 1’s such that at any point, the number of 0’s doesn’t exceed the number of
1’s. This can be done in bn ways where bn denotes the sequence of Catalan numbers. Accordingly, the
number of drawings of ‘n’ semicircles in such a way that no two semicircles are intersecting is given by the
Catalan number bn. ------4 marks.
*******************************************
| Website for students | VTU NOTES