Given a graph, decide if its edge connectivity is at least n/2 or not
You can easily check this in linear time, since a graph has edge
connectivity at least $n/2$ if and only if its minimum degree is at
least $n/2$. You already argued for the “only if” part. Consider now a
graph where every vertex has degree at least $n/2$ and a cut that
divides the graph into two vertex sets $X$ and $\bar X$ with $x := |X|
\leq n/2$. A vertex in $X$ can have at most $x - 1$ connections to
other vertices in $X$, and thus must contribute at least $n/2 - (x -
1)$ edges to the cut. Thus, the cut must have size at least $x (n/2 -
x + 1)$. It remains to show that $x (n/2 - x + 1) \geq n/2$, which is
true since $(x - 1)(n/2 - x) \geq 0$.

Strangely enough, the only reference I find to this result is this from a bioinformatics conference. I'd be really curious to see whether it has been proven somewhere else.

Edit: An earlier reference is: Gary Chartrand: A Graph-Theoretic Approach to a Communications Problem, SIAM J. Appl. Math. 14-4 (1966), pp. 778-781.