# Graphs with no homomorphism and no minor relation

What is an example of two simple, undirected graphs $G,H$ such that

• there are no graph homomorphisms between $G, H$, and
• $H$ is not a minor of $G$, and $G$ is not a minor of $H$

?

Definition of minor: Let $G$ be a simple undirected graph. If $S, T$ are disjoint subsets of $V(G)$ we say that $S, T$ are connected to each other if there is $s\in S, t\in T$ such that $\{s,t\}\in E(G)$. If $G,H$ are graphs, we say $H$ is a minor of $G$ if there is a family ${\cal S}$ of pairwise disjoint connected subsets of $V(G)$ and a bijection $\varphi:V(H)\to {\cal S}$ such that whenever $\{v,w\}\in E(H)$ then $\varphi(v)$ and $\varphi(w)$ are connected to each other.

• $G = K_3$ and $H = C_4$? – Gordon Royle Jun 15 '15 at 7:44
• That's right -- Sorry - I meant the symmetric relation (not an image of each other, not a minor of each other), will correct this – Dominic van der Zypen Jun 15 '15 at 8:18