Skip to main content
1 of 2
Pablo
  • 11.3k
  • 2
  • 22
  • 68

Removing subtrees

Let $T$ be a complete infinite rooted binary tree. Is it possible to remove (infinitely many) subtrees of $T$ and get a subgraph $G$ such that:

  1. $G$ has no complete subtrees (the graph below any vertex of $G$ is not a complete binary tree).

  2. There exists some $\epsilon > 0$ such that for any $n \in \mathbb{N}$ the number of vertices of $G$ whose distance from the root is $n$ is at least $\epsilon2^n$.

Pablo
  • 11.3k
  • 2
  • 22
  • 68