The starting point of this question is the fact that for some simple, undirected graphs $G, H$ there is no graph homomorphism $f:G\to H$. This is the case for instance if $\chi(G)>\chi(H)$.


Informally speaking, the bit below is about how "close" a map between the vertex sets of graphs can become to being a graph homomorphism.


More formally, given (finite or infinite) graphs $G, H$ and a **function** $f:V(G)\to V(H)$ we say that $e\in E(G)$ is *faulty* with respect to $f$ if $\text{im}(f|\_e) = f(e) \notin E(H)$, be it because $f(e)$ only consists of $1$ element, or be it because $f(e)$ consists of two non-adjacent vertices of $H$.


Let $\text{Flt}(G, H)$ consist of those sets $T\subseteq E(G)$ such that there is a map $f:G\to H$ such that $T$ is the collection of faulty edges with respect to $f$. We call the members of $\text{Flt}(G,H)$ *faulty edge sets*.


**Question.** When we consider the poset $(\text{Flt}(G,H),\subseteq)$, does every faulty edge set contain a minimal faulty edge set?



Minimizing the set of "faulty" edges in a map between the vertex sets of $2$ graphs
Let $G=K\_\omega$ be a clique on infinitely many vertices and $H$ a disjoint union of $K\_n$ for each $n\in\omega$. I claim $\text{Flt}(G,H)$ has no minimal elements.


Let $f:V(G)\to V(H)$ be arbitrary. Take some vertices $v,w\in V(G)$ with $f(v)\in K\_n$ and $f(w)\in K\_m$ with $n\neq m$. Consider a map $g:V(H)\to V(H)$ which does the following: if $k\neq n,m$ and is not a multiple of $n+m$, then $g|\_{K\_k}$ is constant. If $k$ is a multiple of $n+m$, then map $K\_k$ to $K\_{k+n+m}$ in an arbitrary, injective way. Lastly, let $g$ map $K\_n$ and $K\_m$ into $K\_{n+m}$ injectively such that their images are disjoint.


Clearly $g$ is a graph homomorphism, from which is follows that if $e\in E(G)$ is not faulty with respect to $f$, it also isn't with respect to $g\circ f$. However, $vw$ is faulty with respect to $f$, but not with respect to $g\circ f$. Therefore the faulty edges of $g\circ f$ are a proper subset of faulty edges of $f$.


