Skip to main content
2 of 2
fix tags
Bjørn Kjos-Hanssen
  • 24.8k
  • 3
  • 58
  • 114

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