# Does the Chen-Chvátal Conjecture on metric spaces hold for maximal lines?

A conjecture by Chen and Chvátal asks for the minimum number of induced "lines" in a metric space, in the same spirit as the De Bruijn–Erdős theorem.

Though the statement of this problem on Douglas West's page on the conjecture asked about lines, I was wondering if any work had been done on the problem with maximal lines (which are not a proper subset of another line) but lack the resources to check. It would be easier to disprove than the original conjecture, but I was wondering if there was an easy counterexample before hitting it over the head with a computer?

The following is the distance function for a metric space with five points.

$$\begin{array}{r|cccc} d & 0& 1& 2& 3& 4\\ \hline 0& 0& 3& 2& 3& 2\\ 1& 3& 0& 3& 2& 3\\ 2& 2& 3& 0& 5& 4\\ 3& 3& 2& 5& 0& 3\\ 4& 2& 3& 4& 3& 0\\ \end{array}$$

It has the following three maximal lines: $$\{\{0, 2, 3, 4\}, \{1, 4\}, \{0, 1, 2, 3\}\}$$

For example the line of $1$ and $2$ is $\{1,2,3\} \subset \{0, 1, 2, 3\}$.

For those who wish to test this digitally, here is the distance function as a list of lists.

[[0,3,2,3,2], [3,0,3,2,3], [2,3,0,5,4], [3,2,5,0,3], [2,3,4,3,0]]

• Nice. I double-checked (by hand), and it looks correct. – Tony Huynh May 19 '16 at 23:06