On the Maximum Number of Spanning Trees in a Planar Graph With a Fixed Number of Edges: A Linear-Algebraic Connection
Alan Bu’s math project gave precise limits on how many spanning trees a planar graph can have. A spanning tree is the connecting point of vertices in a graph. His key insight was to connect the spanning tree counting problem to a separate problem in linear algebra, a different field of math, which he could then attack. His results shed light on the structure of planar graphs.
View PosterAlan Bu, 17, of Glenmont, New York, made connections between graph theory and linear algebra for his Regeneron Science Talent Search mathematics project. Alan’s project provides precise limits on the number of spanning trees a planar graph, a graph in which no edges cross each other, can have. A spanning tree is a minimal selection of edges that connects all the objects in a graph. Mathematical graphs are used to represent and study objects and how they relate to each other, such as how molecules form lattices in solids.
Knowing the number of spanning trees of a graph gives important insights into its structure, which can then be used in applications. Previous work had estimated this number, but Alan made these estimates much more precise. His key insight was to connect the number of spanning trees to a linear algebra problem, a different field of math concerned with matrices.
At Phillips Exeter Academy in Exeter, New Hampshire, Alan is co-head of the school’s chess team, the science bowl club, and volunteered as a peer tutor. As director of math club competitions, he has connected with hundreds of middle school students from across the U.S. and China. Alan is the son of Ye Zhong and Huiming Bu.
Beyond the Project
Alan runs the school’s math club and says it “isn’t just about handouts, competitions, AMC preparation, and weekly meetings: it lives in the people who come each week.”
FUN FACTS: Alan loves playing cards: tractor, poker, mahjong, fish, everything under the sun and all are free to join in. He’s looking for old card games that grandparents might have played so he can learn them!