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.
Best Answer
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.