The problem statement isnâ€™t â€śmisleadingâ€ť, itâ€™s *entirely incorrect* however you interpret it.

@ushsh, both the pre-edit and post-edit versions of the problem are wrong. The edit just rewrote the sentence while for the most part maintaining its meaning.

Easy example: for n=4, m=5, the graph can ALWAYS be drawn by **choosing** (it said you could choose points from the euclidean plane) the 4 points to be the vertices of a square and the 5 edges to be its outer edges and one diagonal, in which case you can ** never ** draw the 6th edge, making the answer 1 in this case. Every graph with (4,5) is isomorphic to the graph described in this embedding.

** PRE-EDIT VERSION **

* â€¦ He marked N pairwise different points on the plane and then connected M pairs of these points by straight-line segments. None of these segments intersect(maybe except at the initial N points). Then Leha tried to draw the M+1-th segment but surprisingly it turned out that it was impossible to connect any pair of points by straight-line segment which wouldnâ€™t intersect with any of the previous segments.*

â€¦

The questions is: whether itâ€™s possible to choose N points on the Euclidean plane such that they will fit the situation described above.

Yes, itâ€™s possible to choose points as described above. You said â€śis it possible to chooseâ€ť. This means you are allowed to ** choose any planar embedding**, even one that would prevent you from adding another edge.

** POST-EDIT VERSION **

* The question is: whether itâ€™s possible to choose N points on the Euclidean plane *** in any way **such that they will ** always ** fit the situation described above.

** Yes, it is ***possible to choose* points â€śin any wayâ€ť (as described above) such that they will â€śalwaysâ€ť fit the situation. â€śAny wayâ€ť means â€śany one way out of all possible waysâ€ť. By saying â€śalwaysâ€ť, the author obviously meant to say (as we realized after some WAs), output 1 if

(i) there exists at least one choice of points with a corresponding planar embedding, and

(ii) considering all graphs (>= 0 of them) resulting from an edge addition to the input graph, none of them has a choice of points corresponding to a planar embedding.

That is, is the graph maximal planar. Totally different question.

Making some words in a sentence bold does not change their meaning. Linguistic accuracy is the foundation of making problem statements, as all of mathematics and computer science depend on formal notation and on ** rigour in language**.

I understand that the problem was probably translated from another language, but that definitely does not justify its being incorrect after testing. I know this is a pretty long rant, but I wasted a lot of time on this problem (as I did with the authorâ€™s previous problem LPARTY a few months ago, which also had a terrible choice of words and story).

I do hope I am correct and would appreciate it if someone could explain how I am wrong in case I am.