Mathematics — Graph Theory · injective-map-vertices-to-edges
Problem
Let G=(V,E,φ) be a connected multigraph such that ∣E∣≥∣V∣. Show that there exists an injective map f:V→E such that for each vertex v∈V, the edge f(v) contains v.
(In other words, show that we can assign to each vertex an edge that contains this vertex in such a way that no edge is assigned twice.)