Let $G_n$ be an undirected graph of $n$ rows with the particular triangular structure.

In the figure above is described $G_3$ .

Let $t_n$ be the minimum number of edges to remove to $G_n$ to make it bipartite .

What is $t_{10^9+8} \bmod {(10^9+7)} ?$

The answer is 0.

**
This section requires Javascript.
**

You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.

My solution is based on an idea from the Wikipedia article -

$\boxed{\text{A bipartite has no odd cycles}}$

Our graph is made up of lots of little 3 vertex triangles. If we look only at those which are the right way up, (in other words they are not balanced on a vertex), we can see that none of the little right way up triangles have an edge in common. So we must remove one edge from each of these little triangles to avoid 3 cycles.

Let's choose to remove the horizontal edge in each little triangle. As an unexpected bonus notice that there are now no odd cycles of any order! This is because as we step along an edge of any cycle in the depleted graph we must move up or down a row (because the horizontal edges have been removed we cannot stay on the same row). To get back where we started the number of steps up must equal the number of steps down, and so the total number of steps must be even. So we do not need to remove any more edges to avoid odd cycles.

Therefore $t_n$ is the number of horizontal edges in $G_n=1+2+\dots(n-1)=\frac{n(n-1)}{2}$

Now we can see that if $n$ is even $t_n$ is a multiple of $(n-1)$ , and so

$t_{10^9+8}\mod{10^9+7}=0$