Sign up or sign in

Contributed Papers

Contributed Papers Session #5.4

Subevent of Contributed Papers Session #5

Times: 2026 Mar 28 from 11:00AM to 11:15AM (Central Time (US & Canada))

Counting Trees and Forests in Graphs

Daniel Pinzon <dpinzon@ggc.edu>, Georgia Gwinnett College

Abstract:

A graph is a finite number of points(vertices) connected by edges. Graphs are used to model computer networks, business competitiveness, organic molecules, social media, logistics, computability, machine learning, etc. as well as being very useful in solving difficult theoretical problems in combinatorics and other mathematical fields. A spanning tree is a subgraph that contains all the vertices, but only some of the edges so that there are no cycles. This means that once you leave a vertex, you cannot return to that point unless you retrace your path. The Matrix-Tree Theorem states that if we represent the graph as an integer valued matrix, called a Laplacian, then its minor gives the number of spanning trees in the graph. This is useful not only in mathematics theories, but in questions about structure and reliability of the network. What is not very well known are questions such as: How many ways can you construct two disjoint subtrees (a 2-forest) where one vertex is in one tree and two others are in the other that together span all the vertices of the graph? There are many questions such as these that are unknown that can be answered by students as an undergraduate research project. We will explore what tools are needed to answer these questions using graph theory, linear algebra, abstract algebra, and mathematics software.

Back to events