Register

CMI2021-A: 4

• edited by
436 views
0 0 votes

Consider the following statements about finite simple graphs $\text{G}$ :

  1. If each vertex of a graph $\text{G}$ has degree at least $2$ then $\text{G}$ contains a cycle as a subgraph.
  2. If the number of edges of a graph $\text{G}$ is at least as large as the number of its vertices, then $\text{G}$ contains a cycle as a subgraph.

Which of the above two statements holds for all graphs?

  1. $(i)$ only

  2. $(ii)$ only

  3. both $(i)$ and $(ii)$

  4. neither of them

Please log in or register to answer this question.

Voting & Accepting an answer helps improve the community
← Previous · CMI2021-A: 5Next → · CMI2021-A: 3
← Previous in category · CMI2021-A: 5Next in category → · CMI2021-A: 3
Position:
Show:

Related questions

1 1 vote
1 1 answer
433
433 views
admin asked Jul 22, 2022
433 views
CMI2021-A: 1
If the milkman doesn’t deliver milk or the geyser doesn’t work, then Akash will be late for school and lunch will be cooked late. Suppose lunch was actually cooked on tim...
0 0 votes
0 0 answers
301
301 views
admin asked Jul 22, 2022
301 views
CMI2021-A: 2
Let $\text{L}$ be the language over $\left \{ a, b \right \}$ that contains the same number of occurrences of $a$ and $b$. Which of the following languages is regular?$\t...
0 0 votes
0 0 answers
293
293 views
admin asked Jul 22, 2022
293 views
CMI2021-A: 3
Which of the following regular expressions represents binary strings that are multiples of $3?$ Note that we consider the leftmost bit to be the most significant.$((11)0^...
0 0 votes
1 1 answer
354
354 views
admin asked Jul 22, 2022
354 views
CMI2021-A: 5
One day, Dumbledore assigns Harry Potter the task of obtaining the Philosopher’s Stone that lies in an inner chamber surrounded by many rooms. To guide him along, he is g...