0
$\begingroup$

For any set $X$ we set $[X]^2 = \big\{\{x,y\}: x\neq y\in X\big\}$.

What is an example of a connected graph $G=(V,E)$ and a subset $S\subseteq V$ such that the subgraph $$G[S]:=(S, E\cap [S]^2)$$ is connected, and there is a surjective graph homomorphism $f:G[S]\to G$, but $G[S]\not\cong G$?

$\endgroup$
  • $\begingroup$ Let $S$ be the infinite tree where each node has $3$ descendants; let $G$ be the tree where the first node has $2$ descendants, each isomorphic to $S$. $\endgroup$ – user44191 Feb 25 at 22:41
1
$\begingroup$

Let $G$ be the graph obtained by subdividing each edge of $K_{1,\aleph_0}$ with one subdivision point, and let $S$ be the set obtained by removing from $V(G)$ one vertex of degree $1$.

$\endgroup$

Your Answer

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

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