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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.