By a graph I mean a pair $G = (V, E)$ where $V$ is a set and $E \subseteq \mathcal{P}\_2(V) := \{\{a,b\}: a\neq b \in V\}$. A *graph homomorphism* between graphs $G, H$ is a map $f:V(G)\to V(H)$ such that $\{v, w\}\in E(G)$ implies $\{f(v), f(w)\} \in E(H)$.


We say that a graph homomorphism $u:G\to H$ is *universal* if for every graph homomorphism $f:G\to H$ there is $v \in V$ such that $f(v) = u(v)$.


Is the composition of two universal graph homomorphisms universal?



Universal graph homomorphisms
Ok, try again.


Let $G\_k=W\_{2k+5}\cup W\_{2k+1}$, where $W\_k$ is the wheel with $k$ spokes. Then for $k\ge 3$, every homomorphism $G\_k\to G\_{k-1}$ fixes the hub of the smaller wheel as there is no homomorphism $W\_{2k+1}\to W\_{2k+3}$, and every homomorphism $W\_{2k+1}\to W\_{2k-1}$ fixes the hub.


Now let $\phi\_k:G\_k\to G\_{k-1}$ be injective homomorphisms (so the bigger wheel goes to the bigger wheel, the smaller to the smaller). Each of these is universal by the argument above. But if you you combine $\phi\_{k+1}$ and $\phi\_{k}$, the resulting homomorphism $G\_{k+1}\to G\_{k-1}$ is not universal: just use a homomorphism that switches the wheels.


