A De Bruijn–Erdős Theorem for Chordal Graphs

  • Laurent Beaudou
  • Adrian Bondy
  • Xiaomin Chen
  • Ehsan Chiniforooshan
  • Maria Chudnovsky
  • Vašek Chvátal
  • Nicolas Fraiman
  • Yori Zwols


A special case of a combinatorial theorem of De Bruijn and Erdős asserts that every noncollinear set of $n$ points in the plane determines at least $n$ distinct lines. Chen and Chávtal suggested a possible generalization of this assertion in metric spaces with appropriately defined lines. We prove this generalization in all metric spaces induced by connected chordal graphs.
Article Number