fiire_ice's blog

By fiire_ice, history, 13 days ago, In English

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.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Not sure what I am missing, can anyone help with this please?