TITLE:
Balance in Random Trees
AUTHORS:
Azer Akhmedov, Warren Shreve
KEYWORDS:
Random Trees, Balance, Equicolorable Graphs
JOURNAL NAME:
Open Journal of Discrete Mathematics,
Vol.4 No.4,
October
6,
2014
ABSTRACT: 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.