Maximal proper subgraphs of median graphs

For a median graph G   and a vertex vv of G   that is not a cut-vertex we show that G-vG-v is a median graph precisely when vv is not the center of a bipartite wheel, which is in turn equivalent with the existence of a certain edge elimination scheme for edges incident with vv. This implies a characterization of vertex-critical (respectively, vertex-complete) median graphs, which are median graphs whose all vertex-deleted subgraphs are not median (respectively, are median). Moreover, two analogous characterizations for edge-deleted median graphs are given.