There is a company which operates at least $8$ routes, so let's show that in a graph with $6$ vertices and $8$ edges there is a $4$-cycle. We count the pairs $(x,\{a,b\})$, where $x$ is connected to both $a$ and $b$. Let $d_i,\ i\in\overline{1,6}$ be the degrees of the vertices. By considering each vertex $x$, and for each vertex counting the pairs $a,b$, we find our number to be equal to $\sum\frac{d_i(d_i-1)}2$, which is $\ge 14$ (simple estimate obtained from $\sum d_i=16$ and $6\sum d_i^2\ge (\sum d_i)^2$). Let's show that there are at least two pairs $(a_1,b_1),(a_2,b_2)$ which do not have any common neighbours, if our graph has no $4$-cycles. Assume the contrary. We can find $a,b$ which are connected s.t. they have a common neighbour $c$. Let the other three vertices be $d,e,f$. Now, since there are at least two edges from the group $d,e,f$ to the group $a,b,c$ and we assumed that there was at most one pair of vertices with no common neighbours, we may assume that $a,d$ are connected and have a common neighbour. This neighbour cannot be $b,c$, because then we would have a $4$-cycle, so assume $ad,de,ae$ are edges. We can't add any more edges to the configuration $abcde$ without getting a $4$-cycle, so there are at least two edges from $f$ to this configuration, but we can easily see that this gets us, again, a $4$ cycle. We have thus shown that if there's no $4$-cycle, then there are at least two pairs of vertices with no common neighbours. However, according to the counting argument above, there are at least $14$ pairs of the form $(x,\{a,b\})$ with $xa,xb$ edges, so there must be a pair $a,b$ which appears twice here (since there are totally $15$ pairs), meaning that $a,b$ have at least two common neighbours, and these, together with $a,b$, form a $4$-cycle.

it's not very rigurous.. but here goes... We'll prove that every graph with 6 vertices and 8 edges has at least one cycle of length 4.(from this the conclusion follows). Denote with $d_i$, $i=1,\ldots,6$ the degrees of the vertices. case1. We have a vertex with degree 5. Let's say that $d_1=5$. Now we must connect the vertices $2,3,4,5,6$ with 3 edges. But this means that one will have degree at least 3 (let's say 2, and 2 is connected with 3 and 4). Then 1,3,2,4 is a cycle of length 4. case2. We have a vertex with degree 4. Let's say $d_1=4$ and that 1 is connected with 2,3,4,5. Then between 2,3,4,5,6 there must be 4 more edges. If the vertex 6 has at least two edges with 2,3,4,5 then the 4-cycle is formed. Else, (let's say (6,2) is an edge ) then between 2,3,4,5 we must have 3 edges so at least one will have the degree 2 (with respect to the subgraph $\{2,3,4,5\}$ ) and analogue with the first case the 4 cycle is formed case3. all vertices have their degree at most 3. If $k$ of them has the degree 3 then Then $16 = \sum d_i\le 3k+2(6-k)=k+12$ so $k\ge 4$. Now I think the 4-cycle can be easily found.