Build a graph | Need help with this problem

Revision en3, by fiire_ice, 2025-01-18 12:00:54

I have been revisiting some of the old problems that I once attempted and came across this one:

https://www.hackerearth.com/practice/algorithms/graphs/graph-representation/practice-problems/algorithm/build-a-graph-5f5c6b4a/

I do not understand why the solution is: "No" for n<12, else "Yes"

Please look at the following graph:

https://ibb.co/42ckF3R

It is an unconnected graph with 2 connected components. It has 9 vertices, 9 edges. In first connected component, each of the 4 vertices in the cycle are cut vertices. The other 4 vertices are degree 1. For the second, a single vertex with degree 0.

What am I missing? I think for n<9 it should be "No", else "Yes".

Please help me out on this.

Tags coding, problem, help

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English fiire_ice 2025-01-18 12:00:54 69
en2 English fiire_ice 2025-01-18 11:59:23 69 Tiny change: 'graph:\n\nIt is ' -> 'graph:\n\nhttps://codeforces.me/a577a4/tmp2.png\n\nIt is '
en1 English fiire_ice 2025-01-18 11:58:38 737 Initial revision (published)