Graph Theory and Combinatorics Seminar

Title: Proof of the Erdős–Sós conjecture

Abstract: In 1962 Erdős and Sós conjectured that every graph G on n vertices with average degree greater than k-2 must contain a copy of every tree on k vertices. Recently the conjecture was proved by GPT-6 Astra via an ingenious argument. We present a simplified version of the proof due to Riordan and Scott, and will also classify the extremal graphs G with average degree exactly k-2 that do not contain all trees.