Skip to content
Get started

A vertex that is not a leaf

MediumCombinatorics5 min

Consider all trees on the labelled vertex set {1,2,…,7}\{1, 2, \dots, 7\} (there are 757^5 of them by Cayley's formula). In how many of these trees is vertex 11 not a leaf (its degree is at least 22)?

Show hints (3)+
  1. Which labelled trees encoding counts every tree exactly once?
  2. In the Prüfer sequence a vertex appears (degree minus one) times.
  3. Count trees where label 1 never appears, then complement.

Answer

Reveal answer →

9031

Create a free account to see the full worked solution and track your progress.

Interview format: Prop Trading, Systematic & Data-Driven Trading

Related questions