Two relations for median graphs (Q1841917)

A graph \(G\) with a distance function \(d\) is called a median graph, if for any three vertices \(u,v,w\) of \(G\) there is a unique vertex \(x\) such that \(d(u,v)=d(u,x)+d(x,v)\), \(d(u,w)=d(u,x)+d(x,w)\), and \(d(v,w)=d(v,x)+d(x,w)\). Trees and hypercubes are median graphs. The author shows that for median graphs \(\sum_{i\geq 0}(-1)^iq_i=1\), where \(q_i\) denotes the number of subgraphs isomorphic to the hypercube \(Q_i\). This is a generalization of the well-known identity \(n-m=1\) for trees. The author also presents an explicit formula for the number \(k\) of \(\Theta\)-classes in a median graph as \(k=-\sum_{i\geq 0}(-1)^iiq_i\).