Author(s)

Azer Akhmedov^*, Warren Shreve

Department of Mathematics, North Dakota State University, Fargo, ND, USA.

We prove that a random labeled (unlabeled) tree is balanced. We also prove that random labeled and unlabeled trees are strongly k-balanced for any k ≥ 3. Definition: Color the vertices of graph G with two colors. Color an edge with the color of its endpoints if they are colored with the same color. Edges with different colored endpoints are left uncolored. G is said to be balanced if neither the number of vertices nor and the number of edges of the two different colors differs by more than one.

Random Trees, Balance, Equicolorable Graphs

Akhmedov, A. and Shreve, W. (2014) Balance in Random Trees. Open Journal of Discrete Mathematics, 4, 97-108. doi: 10.4236/ojdm.2014.44013.