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?

  • $\begingroup$ What do you mean with a function between two graphs? A function between vertex sets? $\endgroup$
    – Wojowu
    Feb 15, 2019 at 20:01
  • $\begingroup$ Good point. I mean a function between the vertex sets. I will correct this $\endgroup$ Feb 15, 2019 at 20:02

1 Answer 1


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.