“if a connected graph with $n$ vertices has at most $αn$ edges, then $G$ is planar.” For what real numbers $α$ is this statement always true? Prove your answer in both directions.
I tried to use $f\le \frac23m$ but still can not find the value of $α$ ...
Note that we can satrt with a $K_5$ and add $m$ edges and $m$ vertices and obtain a non-planar graph. This shows that the statement is wrong for any $\alpha>1$ if we make $m$ big enough.
If $\alpha\le 1$, then the graph is planar: Recall that a connected graoh with $n$ vertices and $n-1$ edges is a tree, so a connected graph with $\le n$ edges is either a tree or has a single cycle, both kinds are clearly planar.