# Graphs admitting an 1-Lipschitz map from edge mid-points to vertices

Let $$G=(V,E)$$ be a graph. A 1-Lipschitz vertex projection is a map $$p: E \to V$$ such that $$p(e)$$ is always an end-vertex of $$e$$, and if $$e,f$$ have a common end-vertex, then $$p(e)$$ and $$p(f)$$ coincide or share an edge. The name is motivated by noticing that if we think of $$G$$ as an 1-complex, with each edge having length 1, and we think of $$p$$ as mapping midpoints of edges to $$V$$, then this map is 1-Lipschitz iff the aforementioned condition is satisfied.

Main Question Which graphs admit an 1-Lipschitz vertex projection?

It is easy to see that trees, cycles, and cliques do. Not every graph does (try e.g. piecing 4-cycles together).

Question 2: Does every chordal graph admit an 1-Lipschitz vertex projection?

• Don't you mean that an edge should be mapped to its endpoint? Otherwise you can map everything to one vertex. Aug 30 at 12:20
• Yes, sorry, I'm amending the question. Aug 30 at 13:09

I assume that $$p$$ should map each edge to one of its endpoints. Under this assumption, any vertex projection $$p\colon E\to V$$ corresponds to orientation of all edges (edge $$e$$ is oriented towards $$p(e)$$), and the 1-Lipschitz condition means that the out-neighbours of any vertex form a clique. So the existence of a 1-Lipschitz projection is equivalent to existence of such orientation.