Scribd
Upload
11 views

Graph Theory2024

The document is an examination paper for a Graph Theory and Combinatorics course at Harish Chandra PG College. It contains a series of questions related to combinatorics, graph properties, and generating functions, with multiple-choice answers provided. The exam is scheduled for June 6, 2024, for BCA IV semester students.

Uploaded by

praveenyadavjmd1507
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
11 views

Graph Theory2024

The document is an examination paper for a Graph Theory and Combinatorics course at Harish Chandra PG College. It contains a series of questions related to combinatorics, graph properties, and generating functions, with multiple-choice answers provided. The exam is scheduled for June 6, 2024, for BCA IV semester students.

Uploaded by

praveenyadavjmd1507
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

FACULTY OF MANAGEMENT AND TECHNOLOGY

HARISH CHANDRA PG COLLEGE, BAWAN BEEGHA VARANASI


Subject: Graph Theory and Combinatorics Meeting:II
Student Name: Roll No:

( Paper code:BCA-S210E1)
Time:-(11:30-12:30) Class:BCA-IV SEM Date:06/06/24
Invigilator’s sign

1. From a group of 7 men and 6 women, how many ways can a committee of 5 people be
formed with at least 3 men?
- a) 756 b) 735 c) 462 d) 525
2. What is the chromatic number of a complete graph with n vertices?
- a) 2 b) n c) n-1 d) 1
3. What is the chromatic number of a bipartite graph?
- a) 2 b) 3 c) 4 d) 1
4. How many colors are needed to color a planar graph according to the Four Color Theorem?
a) 2 b) 3 c) 4 d) 5
5. What is the chromatic number of a tree with n vertices?
a) 1 b) 2 c) 3 d) n-1
3 5
6. What is the coefficient of x in the expansion of (1 + x) ?
a) 5 b) 10 c) 20 d) 30
7. What is the generating function for the sequence 1, 2, 4, 8, ...?
a) 1/(1 - 2x) b) 1/(1 + 2x) c) x/(1 - x) d) 2/(1 - x)
8. How many different ways can a group of 4 students be chosen from 10 students?
a) 210 b) 252 c) 120 d) 45
9. What is the chromatic number of a wheel graph with 5 vertices?
a) 2 b) 3 c) 4 d) 5
10. What is the chromatic number of a bipartite graph with an odd number of vertices?
a) 2 b) 3 c) 4 d) 1
11. What is the coefficient of x2 in the expansion of (1 + x)4?
a) 6 b) 4 c) 3 d) 1
12. What is the sum of the coefficients in the expansion of (x + 1)8?
a) 128 b) 256 c) 512 d) 1024
13. What is the generating function for the sequence 1, 1, 1, 1, ...?
a) 1/(1 - x) b) x/(1 - x) c) 1/(1 + x) d) x/(1 + x)
14. What is the generating function for the sequence 0, 1, 1, 1, ...?
a) 1/(1 - x)2 b) x/(1 - x) c) x/(1 - x)2 d) 1/(1 + x)
15. What is the generating function for the sequence 1, -1, 1, -1, ...?
a) 1/(1 + x) b) 1/(1 - x) c) x/(1 + x) d) x/(1 - x)
16. From a group of 5 men and 6 women, how many ways can a committee of 4 people be
formed with at least 2 men?
a) 756 b) 735 c) 462 d) 525
17. How many ways can a team of 3 people be chosen from a group of 7?
a) 210 b) 252 c) 120 d) 35
18. What is the chromatic number of a complete bipartite graph K3,3?
a) 2 b) 3 c) 4 d) 6
19. What is the chromatic number of a complete graph K5?
a) 5 b) 4 c) 3 d) 2

20. Find the number of permutations of the letters of the word ALLAHABAD.
a)7560 b)7650 c)7660 d)7550
21. Which of the following is not a type of directed graph?
a) Tree b) Directed acyclic graph (DAG)
c) Directed connected graph d) Directed cyclic graph
22. If you have 4 distinct elements and you want to arrange them in sets of 3 with unlimited
repetition, how many permutations are possible?
a) 12 b) 64 c) 81 d) 192
23. What is a matching in a graph?
a) A set of edges with no common vertices b) A set of vertices with no common edges
c) A set of edges with common vertices d) A set of vertices with common edges
24. In a bipartite graph, a matching that covers all vertices of one partite set is called:
a) Maximum matching b) Perfect matching c) Minimum matching d) Complete matching

25. For the generating function G(x)=1/(1 − 3𝑥) , what is the coefficient of x4?

a) 1 b) 3 c) 9 d) 27

1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25

Student’s Sign_____________________________________________

Examiner’s Sign____________________________________________

You might also like