A characterization of graphs of diameter two with fewer lines than vertices

Martín Matamala

In 2008 Chen and Chvátal conjectured that any metric space on n points has at least n lines, unless all the points belong to one line. Chv\atal proved in 2014 that this is indeed t…