Median Graphs and Triangle-Free Graphs

Let M (m, n) be the complexity of checking whether a graph G with m edges and n vertices is a median graph. We show that the complexity of checking whether G is triangle-free is at most O(M(m, m)). Conversely, we prove that the complexity of checking whether a given graph is a median graph is at most O(m log n + T(m log n, n)), where T(m, n) is the complexity of finding all triangles of the graph. We also demonstrate that, intuitively speaking, there are as many median graphs as there are triangle-free graphs. Finally, these results enable us to prove that the complexity of recognizing planar median graphs is linear.