Question 19
Let G be a simple graph with 25 vertices and 50 edges. The size of the minimum vertex cover of G is 10. What is the size of the maximum independent set of G ?
65
90
15
35
Question 19: Let G be a simple graph with 25 vertices and 50 edges. T…
Show answer
Correct answer
15
Question 19 of 24 in the IIT Madras BS Programming in Python (Python) End Term paper sat on 10 May 2026, in the January 2026 term (Programming In Python 06 May 26). It carries 4 marks.
This question was also asked in
More questions from this paper
- Consider the following function: If the function is called as: What value will the function return?
- In a binary tree, the total number of nodes is 28. It is known that 10 nodes have exactly two children. How many nodes …
- While inserting the elements 60, 30, 50, 55, 80, 90, 65, 70, and 10 into an empty binary search tree (BST) in the seque…
- An entire message is created using characters from the set The probability of occurrence of each character is given in …
- In a list , two elements and form a significant inversion if and . The total number of significant inversions for is _ .
- Arrange the above functions in increasing order of asymptotic complexity.
- A list of strings, each of length is sorted in lexicographical order using the Merge Sort algorithm. What is its time c…
- Consider that Quick sort is applied on a list of size which is sorted in reverse order . What will be the asymptotic ru…
- Consider the following class : Consider an implementation of a linked list where each node is created using the given c…
- Consider the following undirected graph . Run BFS starting from vertex A. If multiple adjacent vertices exist, they are…
- Consider a connected, directed graph on which DFS is executed. and numbering is used in the DFS algorithm on the graph.…
- The Bellman-Ford algorithm cannot be used if a graph has negative cycles. This is because:
- While inserting the elements 8, 4, 1, 3, 9, 2, and 11 in an empty AVL tree in the given sequence, the leaf elements are.
- Consider the following activities . We can execute one activity at a time. Each activity has activity duration , which …
- Consider the following recurrence relation for an algorithm: with base case . The complexity of this algorithm is _
- Consider four matrices and of dimensions and respectively. If and , then which of the following takes the least time fo…
- Assume there are teachers and 2n subjects. Each teacher has to teach exactly 2 subjects. Their preferences are modelled…
- A factory produces two types of gadgets A and B. The profit earned is Rs. 6 per unit of A and Rs. 4 per unit of B. Each…
- A hash table of size 10 uses open addressing with linear probing and the hash function After inserting 6 keys into an e…
- A technology training institute offers an advanced certification program consisting of 10 modules. The program is divid…
- There are stones, numbered . For each , the height of Stone is . There is a frog who is initially on Stone . He will re…
- Consider the following graph. Which of the following options correctly represents the shortest distances from node 0 to…
- Consider the graph G given below. Let Minimum Spanning Trees (MSTs) of the graph be constructed using algorithms such a…