The problem statement isn't "misleading", it's <b><i>entirely incorrect</i></b> 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 <i><b>choosing</b> (it said you could choose points from the euclidean plane)</i> 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 <b> never </b> 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.
<b> PRE-EDIT VERSION </b>
<i> ... 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. </i>
Yes, it's possible to choose points as described above. You said "is it possible to choose". This means you are allowed to <b> choose any planar embedding</b>, even one that would prevent you from adding another edge.
_________________
<b> POST-EDIT VERSION </b>
<i> The question is: whether it's possible to choose N points on the Euclidean plane <b> in any way </b>such that they will <b> always </b> fit the situation described above. </i>
<b> Yes, it is <i>possible to choose</i> points "in any way" (as described above) such that they will "always" fit the situation. </b> "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 ~~exist ~~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 <b> rigour in language</b>.
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.