The Problems of Testing Whether a Graph Is a Mediangraph, and Whether a Graph Is Triangle-Free, Both Had Been Well Studied Whenimrich, Klavžar & Mulder (1999) Observed That, In some Sense, They Arecomputationally Equivalent. Therefore, the Best Known Time Bound Fortesting Whether a Graph Is Triangle-Free, O(M1.41), Applies As Well to Testing Whether a Graph Isa Median Graph, and any Improvement In Median Graph Testing Algorithms Wouldalso Lead to an Improvement In Algorithms For Detecting Triangles In Graphs. In One Direction, Suppose One Is Given As Input a Graph G, and Must Test Whether G Is Triangle-Free. from G, Construct a New Graph H Having As Vertices Each Set Ofzero, One, or Two Adjacent Vertices of G. Two Such Sets Are Adjacent In Hwhen They Differ By Exactly One Vertex. an Equivalent Description of H Is That It Is Formed By Splittingeach Edge of G into a Path Oftwo Edges, and Adding a New Vertex Connected to All the Original Vertices of G. This Graph H Is By Construction a Partial Cube,But It Is a Median Graph Only When Gis Triangle-Free: If A, B, and C Form a Triangle In G,Then {A,B}, {A,C}, and {B,C} Have Nomedian In H, For Such a Medianwould Have to Correspond to the Set {A,B,C}, But Sets of Three or More Vertices of G Do Not Form Vertices In H. Therefore, G Is Triangle-Free If and Only If H Is a Median Graph. In Thecase That G Is Triangle-Free, H Is Its Simplex Graph. Analgorithm to Test Efficiently Whether His a Median Graph Could By This Construction Al ...