# Minimizing the set of “faulty” edges in a map between the vertex sets of $2$ graphs

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?

• What do you mean with a function between two graphs? A function between vertex sets? – Wojowu Feb 15 '19 at 20:01
• Good point. I mean a function between the vertex sets. I will correct this – Dominic van der Zypen Feb 15 '19 at 20:02

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$$.