Codex Wiki OurBigBook logoOurBigBook.comSite Source code
Partition the vertices into two sets of comparable size. If , the first set contains a triangle with probability tending to one. Conditional on any triangle chosen using only internal edges, the probability that none of its vertices has a neighbour in the second set is at most
Hence contains a triangle with an attached leaf with probability tending to one.

Ancestors (6)

  1. Binomial random graph
  2. Graph theory
  3. Foundations of mathematics
  4. Area of mathematics
  5. Mathematics
  6. Home