Addressing a question posed by Erdős and Hajnal, Chen and Ma proved that, for all , the complete bipartite graph is the unique graph on vertices with at least edges that contains no two vertices of equal degree joined by a path of length three. In this paper, we extend this result and prove that for every fixed integer and sufficiently large , the unique -vertex graph with at least edges that contains no two vertices of equal degree joined by a path of length is the half graph . This resolves the problem posed by Chen and Ma, as well as a related question of Attwa, Azócar Carvajal, Boyadzhiyska, Pierron, and Taraz concerning paths of even length with equal-degree endpoints.

生成讲解博客的中文版本

生成AI智能校验的中文版本