Back to Subject

Unit 2: Graphs and Combinatorics - Practice Quiz

CSE333 — Combinatorial Studies-I 60 Questions
0 Correct 0 Wrong 60 Left
0/60

1 When is an undirected graph called connected?

connectivity Easy
A. When every vertex belongs to a cycle
B. When every pair of vertices is adjacent
C. When every pair of vertices is joined by a path
D. When every vertex has the same degree

2 What is a connected component of a graph?

connectivity Easy
A. A maximal connected subgraph
B. A minimal complete subgraph
C. A maximal independent set
D. A minimal spanning tree

3 What is a cut-vertex of a connected graph?

connectivity Easy
A. A vertex whose degree is always zero
B. A vertex that belongs to every cycle
C. A vertex connected to every other vertex
D. A vertex whose removal disconnects the graph

4 How many connected components does a connected graph have?

connectivity Easy
A.
B.
C.
D.

5 What is a matching in a graph?

matching Easy
A. A set of edges forming one cycle
B. A set of edges with no common endpoints
C. A set of vertices joined pairwise
D. A set of vertices with equal degrees

6 What is a perfect matching?

matching Easy
A. A matching containing every edge
B. A matching using only cycle edges
C. A matching covering every vertex
D. A matching forming a complete graph

7 If a matching contains edges, how many vertices does it cover?

matching Easy
A.
B.
C.
D.

8 What is a proper vertex coloring of a graph?

coloring Easy
A. A coloring where all vertices have different colors
B. A coloring where adjacent vertices have different colors
C. A coloring where all cycles have one color
D. A coloring where adjacent edges have equal colors

9 What does the chromatic number represent?

coloring Easy
A. The number of vertices contained in the graph
B. The minimum colors needed for a proper vertex coloring
C. The number of edges contained in the graph
D. The maximum colors allowed in an edge coloring

10 What is the chromatic number of a nonempty bipartite graph containing at least one edge?

coloring Easy
A.
B.
C.
D.

11 According to the addition principle, if one task can be done in ways and a separate alternative task in ways, how many choices are possible?

counting Easy
A.
B.
C.
D.

12 How many permutations are there of distinct objects?

counting Easy
A.
B.
C.
D.

13 How many ways can objects be selected from distinct objects when order does not matter?

counting Easy
A.
B.
C.
D.

14 A menu offers starters and main courses. How many starter-and-main-course meals can be formed?

counting Easy
A.
B.
C.
D.

15 What does a recurrence relation describe?

recurrence relations Easy
A. A set using only repeated elements
B. A function using only constant values
C. A graph using only isolated vertices
D. A term using earlier terms of a sequence

16 Given and , what is ?

recurrence relations Easy
A.
B.
C.
D.

17 Which recurrence relation defines the Fibonacci sequence when and ?

recurrence relations Easy
A.
B.
C.
D.

18 What is the ordinary generating function of a sequence ?

generating functions Easy
A.
B.
C.
D.

19 What sequence is represented by the generating function ?

generating functions Easy
A.
B.
C.
D.

20 For , which expression equals the generating function ?

generating functions Easy
A.
B.
C.
D.

21 A connected graph consists of two cycles that share exactly one vertex and have no other vertices or edges in common. What is the vertex connectivity of the graph?

connectivity Medium
A.
B.
C.
D.

22 A connected graph has vertices and edges. How many edges must be removed to obtain a spanning tree?

connectivity Medium
A.
B.
C.
D.

23 For two nonadjacent vertices and , the smallest set of vertices whose removal separates from has size . What does Menger's theorem imply?

connectivity Medium
A. There are three internally vertex-disjoint - paths
B. Every possible - path must contain all three vertices of the minimum separating set
C. There are four internally vertex-disjoint - paths
D. There are exactly three edge-disjoint cycles containing both vertices

24 What is the size of a maximum matching in the path graph ?

matching Medium
A.
B.
C.
D.

25 In a bipartite graph with parts and , suppose and . What is the maximum matching size?

matching Medium
A.
B.
C.
D.

26 A matching contains an augmenting path with edges. What happens when the matched and unmatched edges along this path are exchanged?

matching Medium
A. The matching size decreases by
B. The matching size increases by
C. The matching size increases by because every edge on the path becomes matched
D. The matching size remains unchanged

27 How many perfect matchings does the complete bipartite graph have?

matching Medium
A.
B.
C.
D.

28 What is the chromatic number of the cycle graph ?

coloring Medium
A.
B.
C.
D.

29 A tree has vertices. How many proper vertex colorings does it have using a palette of labeled colors?

coloring Medium
A.
B.
C.
D.

30 What is the edge chromatic number of the complete graph ?

coloring Medium
A.
B.
C.
D.

31 The vertices of a graph are processed in an order such that each vertex has at most three previously colored neighbors. What does the greedy coloring algorithm guarantee?

coloring Medium
A. A proper coloring with at most colors
B. A proper coloring with exactly colors
C. A proper coloring with at most colors
D. An optimal coloring in which every vertex receives a color different from every vertex processed earlier

32 How many labeled simple graphs on vertices have exactly edges?

counting Medium
A.
B.
C.
D.

33 How many onto functions are there from a -element set to a -element set?

counting Medium
A.
B.
C.
D.

34 How many binary strings of length contain no two consecutive s?

counting Medium
A.
B.
C.
D.

35 A sequence satisfies for , with . Which formula gives ?

recurrence relations Medium
A.
B.
C.
D.

36 Let be the number of ways to tile a rectangle using dominoes. What is ?

recurrence relations Medium
A.
B.
C.
D.

37 What is the general form of a sequence satisfying ?

recurrence relations Medium
A.
B.
C.
D.

38 What is the ordinary generating function for the sequence , where for ?

generating functions Medium
A.
B.
C.
D.

39 What is the coefficient of in ?

generating functions Medium
A.
B.
C.
D.

40 Let and . What is the coefficient of in ?

generating functions Medium
A.
B.
C.
D.

41 Let be the Cartesian product of the cycle and the complete graph . What is the vertex connectivity ?

connectivity Hard
A.
B.
C.
D.

42 A graph is formed from two disjoint copies of by adding three edges between them, with all six endpoints distinct. What is the edge connectivity of the resulting graph?

connectivity Hard
A.
B.
C.
D.

43 Let be a -vertex-connected graph. A new vertex is added and joined to exactly three distinct vertices of . What is the vertex connectivity of the resulting graph ?

connectivity Hard
A. Exactly
B. Exactly
C. At least
D. Exactly

44 A graph has vertices and satisfies where is the number of odd components of . What is the size of a maximum matching in ?

matching Hard
A.
B.
C.
D.

45 The crown graph on bipartition sets and is obtained from by deleting every edge . How many perfect matchings does it have?

matching Hard
A.
B.
C.
D.

46 Which statement must hold for every finite graph that has a unique perfect matching ?

matching Hard
A. The graph contains an even cycle
B. Some edge of is a bridge
C. Every edge of is a bridge
D. The graph is bipartite

47 Let be the wheel obtained by adjoining a universal hub to the cycle . How many proper vertex colorings of use colors from a fixed set of four colors?

coloring Hard
A.
B.
C.
D.

48 Starting with , apply the Mycielski construction twice to obtain a graph . What are and , respectively?

coloring Hard
A. and
B. and
C. and
D. and

49 What is the edge chromatic number ?

coloring Hard
A.
B.
C.
D.

50 Suppose every nonempty subgraph of contains a vertex of degree at most . What is the smallest integer such that is always guaranteed to be -list-colorable?

coloring Hard
A.
B.
C.
D.

51 How many binary necklaces of length contain exactly six s, where necklaces are identified under cyclic rotation but not reflection?

counting Hard
A.
B.
C.
D.

52 How many surjective functions are there from an -element set onto a -element set?

counting Hard
A.
B.
C.
D.

53 How many spanning trees does the complete bipartite graph have?

counting Hard
A.
B.
C.
D.

54 How many permutations of have no fixed points and consist of exactly three disjoint cycles?

counting Hard
A.
B.
C.
D.

55 The sequence satisfies for , with and . Which formula gives ?

recurrence relations Hard
A.
B.
C.
D.

56 Let and for . What is ?

recurrence relations Hard
A.
B.
C.
D.

57 A sequence satisfies for , with and . What is ?

recurrence relations Hard
A.
B.
C.
D.

58 Let and for . What is the ordinary generating function ?

generating functions Hard
A.
B.
C.
D.

59 Which exponential generating function counts set partitions in which every block has size at least ?

generating functions Hard
A.
B.
C.
D.

60 How many integer solutions satisfy with for every ?

generating functions Hard
A.
B.
C.
D.
Previous MCQ
Unit 1
Next MCQ
Unit 3