Extremely difficult graph theory question The following question was on my introduction to combinatorics and graph theory exam. I asked around and it seems no one managed to solve it. I certainly didn't, even now after thinking about it for a few hours. I'd appreiciate any help.

Prove: There is $n_0\in\mathbb{N}$ so that for every $n>n_0$ there are two non-isomorphic graphs, $G_1$ and $G_2$, such that:

*

*$G_1$ and $G_2$ each have $2n$ vertices and $n^2$ edges

*For every integer $k$, $1\le k\le\left \lfloor{\sqrt{n}}\right \rfloor$, the number of simple paths of length $k$ of $G_1$ is equal to the number of simple paths of length $k$ of
$G_2$.


Thanks to anyone who'll give it a try.
 A: This sounds like an interesting problem, although does seem hard for an exam question. 
One idea would be to exploit the fact that you are only interested in relatively short paths, so make sure $G_1$ and $G_2$ differ only on a large scale. For instance consider 6 vertex-disjoint $K_t$'s (where $t$ will be chosen later), each with a distinguished vertex. In $G_1$ connect these vertices with paths of length $\sqrt{n}$ in the form of a hexagon. In $G_2$ do the same, but in the form of two disjoint triangles. 
Now the graphs are 'locally' the same- it is easy to show they have the same numbers of short paths. The only problem is that these graphs have too few edges. So on the remaining $2n-6(t+\sqrt{n})$ vertices, add a component with the required number of edges to $G_1$ and $G_2$. You will have to choose $t$ suitably to make this work, but this is not difficult.
A: I just noticed I didn't post my answer. Better late than never. Apologies. The following answer is based on user264781's insight.
Let $b\in\mathbb{N}$. Let $C_{b\left \lfloor{\sqrt{n}}\right \rfloor}$ be a circle with $b\left \lfloor{\sqrt{n}}\right \rfloor$ vertices. For $1 \le k \le \left \lfloor{\sqrt{n}}\right \rfloor$, there are $b\left \lfloor{\sqrt{n}}\right \rfloor$ paths of length $k$ in $C_{b\left \lfloor{\sqrt{n}}\right \rfloor}$.
Let $K_{2n-6b\left \lfloor{\sqrt{n}}\right \rfloor}$ be a complete graph with $2n-6\left \lfloor{\sqrt{n}}\right \rfloor$ vertices. It has $K_V = {{2n-6\left \lfloor{\sqrt{n}}\right \rfloor} \choose 2} = (n-3\left \lfloor{\sqrt{n}}\right \rfloor)(2n-6\left \lfloor{\sqrt{n}}\right \rfloor -1)$ edges. Also, $\lim\limits_{n\to\infty}\frac{K_V}{n^2-6\left \lfloor{\sqrt{n}}\right \rfloor}  =2$. Therefore $K_V > n^2-6\left \lfloor{\sqrt{n}}\right \rfloor$ for a large enough $n$.
Thus, for $n>N$, let $T(n) = (V, E)$, be a graph with $2n-6\left \lfloor{\sqrt{n}}\right \rfloor$ vertices and $n^2-6\left \lfloor{\sqrt{n}}\right \rfloor$ edges, such that:


*

*$E(T(n)) = E(K_{2n-6\left \lfloor{\sqrt{n}}\right \rfloor}) -A$ for some $A \subset E(K_{2n-6\left \lfloor{\sqrt{n}}\right \rfloor})$, $|A|=6\left \lfloor{\sqrt{n}}\right \rfloor$

*$V(T(n))=V(K_{2n-6\left \lfloor{\sqrt{n}}\right \rfloor})$


Let $G_1$ be the union of the graphs $T(n)$, $C_{3\left \lfloor{\sqrt{n}}\right \rfloor}$ and $C_{3\left \lfloor{\sqrt{n}}\right \rfloor}$. Let $G_2$ be the the union of the graphs $T(n)$ and $C_{6\left \lfloor{\sqrt{n}}\right \rfloor}$.
From our construction, $G_1$ and $G_2$ have exactly $2n$ vertices and $n^2$ edges. Also, they're not isomorphic because they have different number of connectivity components.
Let $f(G, k)$ be the number of paths of length $k$ in graph $G$.And then, for $1 \le k \le \left \lfloor{\sqrt{n}}\right \rfloor$: 
\begin{align}
f(G_1, k)&=f(T(n), k) + 2f(C_{3\left \lfloor{\sqrt{n}}\right \rfloor})\\\\
&=f(T(n), k) + 6\left \lfloor{\sqrt{n}}\right \rfloor\\\\
&=f(T(n), k) + f(C_{6\left \lfloor{\sqrt{n}}\right \rfloor})\\\\
&=f(G_2, k)
\end{align}
$\blacksquare$
