Combinatorics and Graph Theory

Description: This quiz covers fundamental concepts and theorems from Combinatorics and Graph Theory, including counting techniques, permutations, combinations, probability, graph properties, and algorithms.
Number of Questions: 14
Created by:
Tags: combinatorics graph theory counting techniques permutations combinations probability graph properties algorithms
Attempted 0/14 Correct 0 Score 0

In a group of 10 people, how many different ways can you select a committee of 4 people?

  1. 210

  2. 252

  3. 300

  4. 240


Correct Option: A
Explanation:

This is a classic combinatorics problem involving combinations. The formula for combinations is C(n, r) = n! / (n-r)!, where n is the total number of items and r is the number of items to be selected. In this case, n = 10 and r = 4, so C(10, 4) = 10! / (10-4)! = 10! / 6! = 210.

A bag contains 6 red balls, 4 blue balls, and 2 green balls. If you randomly select 3 balls from the bag without replacement, what is the probability of getting exactly 2 red balls and 1 blue ball?

  1. 1/5

  2. 1/10

  3. 1/15

  4. 1/20


Correct Option: B
Explanation:

To solve this probability problem, we can use conditional probability. First, we calculate the probability of selecting 2 red balls from the 6 red balls: P(2 red) = C(6, 2) / C(12, 2) = 15 / 66. Then, given that we have selected 2 red balls, we calculate the probability of selecting 1 blue ball from the remaining 10 balls: P(1 blue | 2 red) = C(4, 1) / C(10, 1) = 4 / 10. Multiplying these probabilities, we get P(2 red and 1 blue) = P(2 red) * P(1 blue | 2 red) = (15 / 66) * (4 / 10) = 1/10.

In a graph with 8 vertices and 12 edges, what is the maximum number of edges that can be added to the graph without creating a cycle?

  1. 3

  2. 4

  3. 5

  4. 6


Correct Option: A
Explanation:

This question relates to the concept of maximum matching in graph theory. According to Tutte's Theorem, the maximum number of edges that can be added to a graph without creating a cycle is equal to the minimum number of vertices that need to be removed to make the graph acyclic. In this case, we can use Tutte's Theorem to find that the maximum number of edges that can be added is 3.

What is the chromatic number of a graph with 4 vertices and 6 edges?

  1. 2

  2. 3

  3. 4

  4. 5


Correct Option: B
Explanation:

The chromatic number of a graph is the minimum number of colors needed to color the vertices of the graph such that no two adjacent vertices have the same color. In this case, the graph has 4 vertices and 6 edges, which means it is a complete graph K_4. The chromatic number of K_4 is known to be 4, so the correct answer is 4.

What is the minimum number of edges that need to be removed from a complete graph with 10 vertices to make it a tree?

  1. 9

  2. 10

  3. 11

  4. 12


Correct Option: A
Explanation:

A tree is a connected graph with no cycles. A complete graph with n vertices has n(n-1)/2 edges. To make a complete graph a tree, we need to remove n-1 edges while maintaining connectivity. Therefore, the minimum number of edges to be removed from a complete graph with 10 vertices to make it a tree is 10-1 = 9.

In a group of 15 people, how many ways can you select a president, a vice president, and a secretary if each person can only hold one position?

  1. 2730

  2. 455

  3. 2205

  4. 3465


Correct Option: C
Explanation:

This is a classic combinatorics problem involving permutations. The formula for permutations is P(n, r) = n! / (n-r)!, where n is the total number of items and r is the number of items to be selected. In this case, n = 15 and r = 3, so P(15, 3) = 15! / (15-3)! = 15! / 12! = 2205.

A company has 10 employees, and 5 of them are women. In how many ways can the company select a team of 3 employees if at least 1 woman must be included?

  1. 252

  2. 120

  3. 132

  4. 105


Correct Option: C
Explanation:

To solve this problem, we can use the principle of inclusion-exclusion. First, we calculate the total number of ways to select a team of 3 employees from 10 employees: C(10, 3) = 10! / (10-3)! = 120. Then, we calculate the number of ways to select a team of 3 employees with no women: C(5, 0) * C(5, 3) = 1 * 10 = 10. Finally, we subtract the number of ways to select a team with no women from the total number of ways to select a team to get the number of ways to select a team with at least 1 woman: 120 - 10 = 110.

A coin is tossed 10 times. What is the probability of getting exactly 5 heads?

  1. 1/1024

  2. 1/256

  3. 1/512

  4. 1/128


Correct Option: B
Explanation:

This is a classic probability problem involving binomial distribution. The formula for binomial distribution is P(x) = (n! / (x!(n-x)!)) * p^x * q^(n-x), where n is the number of trials, x is the number of successes, p is the probability of success, and q is the probability of failure. In this case, n = 10, x = 5, p = 1/2, and q = 1/2. Plugging these values into the formula, we get P(5) = (10! / (5!(10-5)!)) * (1/2)^5 * (1/2)^(10-5) = 252 / 1024 = 1/4.

In a group of 20 people, how many ways can you select a committee of 5 people if 2 specific people must be included?

  1. 15504

  2. 16380

  3. 17280

  4. 18180


Correct Option: D
Explanation:

This is a classic combinatorics problem involving combinations. The formula for combinations is C(n, r) = n! / (n-r)!, where n is the total number of items and r is the number of items to be selected. In this case, we need to select 5 people from a group of 20, but 2 specific people must be included. So, we first select the 2 specific people, which can be done in C(2, 2) = 1 way. Then, we select the remaining 3 people from the remaining 18 people, which can be done in C(18, 3) = 816 ways. Multiplying these values, we get the total number of ways to select a committee of 5 people with 2 specific people included: 1 * 816 = 816.

What is the maximum number of edges that can be added to a graph with 5 vertices and 7 edges without creating a cycle?

  1. 2

  2. 3

  3. 4

  4. 5


Correct Option: A
Explanation:

This question relates to the concept of maximum matching in graph theory. According to Tutte's Theorem, the maximum number of edges that can be added to a graph without creating a cycle is equal to the minimum number of vertices that need to be removed to make the graph acyclic. In this case, we can use Tutte's Theorem to find that the maximum number of edges that can be added is 2.

What is the chromatic number of a graph with 6 vertices and 9 edges?

  1. 2

  2. 3

  3. 4

  4. 5


Correct Option: B
Explanation:

The chromatic number of a graph is the minimum number of colors needed to color the vertices of the graph such that no two adjacent vertices have the same color. In this case, the graph has 6 vertices and 9 edges, which means it is a complete graph K_6. The chromatic number of K_6 is known to be 4, so the correct answer is 4.

What is the minimum number of edges that need to be removed from a complete graph with 8 vertices to make it a tree?

  1. 7

  2. 8

  3. 9

  4. 10


Correct Option: A
Explanation:

A tree is a connected graph with no cycles. A complete graph with n vertices has n(n-1)/2 edges. To make a complete graph a tree, we need to remove n-1 edges while maintaining connectivity. Therefore, the minimum number of edges to be removed from a complete graph with 8 vertices to make it a tree is 8-1 = 7.

In a group of 12 people, how many ways can you select a president, a vice president, and a secretary if each person can only hold one position?

  1. 1320

  2. 1512

  3. 1680

  4. 1848


Correct Option: A
Explanation:

This is a classic combinatorics problem involving permutations. The formula for permutations is P(n, r) = n! / (n-r)!, where n is the total number of items and r is the number of items to be selected. In this case, n = 12 and r = 3, so P(12, 3) = 12! / (12-3)! = 12! / 9! = 1320.

A company has 15 employees, and 6 of them are women. In how many ways can the company select a team of 4 employees if at least 2 women must be included?

  1. 3003

  2. 3150

  3. 3300

  4. 3450


Correct Option: C
Explanation:

To solve this problem, we can use the principle of inclusion-exclusion. First, we calculate the total number of ways to select a team of 4 employees from 15 employees: C(15, 4) = 15! / (15-4)! = 15! / 11! = 1365. Then, we calculate the number of ways to select a team of 4 employees with no women: C(9, 0) * C(6, 4) = 1 * 15 = 15. Finally, we subtract the number of ways to select a team with no women from the total number of ways to select a team to get the number of ways to select a team with at least 2 women: 1365 - 15 = 1350.

- Hide questions