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$
1
  • $\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, 2019 at 22:41

1 Answer 1

0
$\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 and acknowledge you have read our privacy policy.

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