MathDB
spanning tree has an an edge whose adjunction to T produces a simple cycle

Source: IMAR 2016 p3

September 27, 2018
graph theorygraphspanning treecombinatoricscombinatorial geometry

Problem Statement

Fix an integer n≥2n \ge 2, let QnQ_n be the graph consisting of all vertices and all edges of an nn-cube, and let TT be a spanning tree in QnQ_n. Show that QnQ_n has an edge whose adjunction to TT produces a simple cycle of length at least 2n2n.
Back to ProblemsView on AoPS