However, the number of edges cannot be too small: Klavžar, Mulder & Škrekovski (1998) prove that in every median graph the inequality 2n − m − k ≤ 2 holds, where m is the number of edges and k is the dimension of the hypercube that the graph is a retract of.
Az élek számát azonban túlságosan lecsökkenteni sem lehet: (Klavžar, Mulder & Škrekovski 1998) igazolták, hogy minden mediángráfra fennáll a 2n − m − k ≤ 2 egyenlőtlenség, ahol m az élek száma, k pedig a hiperkocka dimenziója, melyből a mediángráf összehúzható.