A generalization of Erdős-Hajnal problem on paths with equal-degree endpoints
Xiamiao Zhao, Yichen Wang, Mei Lu · 2026
Read A generalization of Erdős-Hajnal problem on paths with equal-degree endpoints by Xiamiao Zhao, Yichen Wang, Mei Lu (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-03825.txt.
Introduction
Xiamiao Zhao, Yichen Wang, and Mei Lu settle a conjecture about paths between equal-degree vertices in dense graphs. Erdős and Hajnal asked whether every graph with a certain number of vertices and edges must contain two vertices of equal degree joined by a path of length three. The edge bound is sharp because of the complete bipartite graph. Chen and Ma answered that question affirmatively for large cases in 2026.
Chen and Ma further conjectured that, for sufficiently large graphs, the statement stays true when the path of length three is replaced by a path of any fixed odd length. Zhao and his co-authors confirm that conjecture, extending the equal-degree phenomenon from short paths to all fixed odd lengths.
Catalog record
| CREATOR | Xiamiao Zhao, Yichen Wang, Mei Lu |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 35 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.03825
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A generalization of Erdős-Hajnal problem on paths with equal-degree endpoints Xiamiao Zhao, Yichen Wang, Mei Lu Abstract Erdős and Hajnal proposed a problem that: is it true that every ( 2 n + 1 ) (2n+1) -vertex graph with n 2 + n + 1 n^{2}+n+1 edges contains two vertices of equal degree connected by a path of length three? The edge bound is sharp by the complete bipartite graph K n , n + 1 K_{n,n+1} . Recently, Chen and Ma [Journal of Combinatorial Theory, Series B, 179:1-18, 2026] answered this problem affirmatively for every n ≥ 600 n\geq 600 . In the same paper, they further conjectured that for sufficiently large n n , the statement is true if we replace the path of length three by a path of fixed odd length. In this paper, we confirm their conjecture. Keywords: Erdős-Hajnal conjecture, Degree sequence, Paths. 1 Introduction In 1991, Erdős and Hajnal proposed the following problem. Problem 1.1 (Erdős and Hajnal [ 2 ] ) Is it true that every (2n+1) -vertex graph with n^{2}+n+1 edges contains two vertices of equal degree connected by a path of length three? The problem is also listed as Problem #816 in Thomas Bloom’s collection of Erdős problems 1 1 1 https://www.erdosproblems.com/816 . Recently, Chen and Ma [ 1 ] answered this problem affirmatively for every n\geq 600 . Theorem 1.1 (Chen and Ma [ 1 ] ) Let n\geq 600 . The unique (2n+1) -vertex graph with at least n^{2}+n edges that does not contain two vertices of the same degree joined by a path of length three, is the complete bipartite graph K_{n,n+1} . They actually proved a stronger result since the property of having two vertices of equal degree joined by a path of length three is not a monotone graph property. Moreover, they proved the extremal graph is unique. The bound n\geq 600 was later improved to n\geq 2 by Liu and Zeng [ 4 ] . Chen and Ma also conjectured that the statement is true if we replace the path of length three by a path of odd length. Conjecture 1.2 (Chen and Ma [ 1 ] ) Let \ell\geq 2 be a fixed integer. For sufficiently large n , the maximum number of edges in a graph that does not contain two vertices of the same degree joined by a path of length 2\ell+1 , is at most n^{2}+n . Recently, Liu and Zeng [ 5 ] confirmed the conjecture when \ell=2 for every n\geq 11 . In this paper, we confirm their conjecture when n is sufficiently large. Actually, we have a stronger result, which shows that the K_{n,n+1} is the unique extremal graph. Theorem 1.3 Let \ell\geq 3 be a fixed integer. Let G be a graph on 2n+1 vertices with at least n^{2}+n edges such that no two vertices with the same degree are connected by a path of length 2\ell+1 . When n\geq f(\ell) where f(\ell) is a polynomial function of \ell , we have that e(G)=n^{2}+n and G is the complete bipartite graph K_{n,n+1} . 2 Preliminaries We first introduce some notation. For a graph G , let e(G) be the number of edges in G . For a vertex set S , let G[S] be the subgraph of G induced by S . For two disjoint vertex sets S_{1} and S_{2} , denote by G[S_{1},S_{2}] the bipartite subgraph of G with vertex set S_{1}\cup S_{2} and edges joining vertices in S_{1} and S_{2} . For a vertex v\in V(G) , let N(v)=\{u\in V(G):uv\in E(G)\} , N[v]=N(v)\cup\{v\} , and d(v)=|N(v)| be the degree of v . For a vertex set S\subseteq V(G) , let N_{S}(v)=N(v)\cap S and d_{S}(v)=|N_{S}(v)| . Denote by P_{k} a path on k vertices. We follow the ideas of Chen and Ma [ 1 ] , and Liu and Zeng [ 4 ] . Let G be a graph on 2n+1 vertices with at least n^{2}+n edges such that no two vertices with the same degree are connected by a P_{2\ell+2} . In this paper, we let \ell\geq 3 . Our goal is to prove that e(G)=n(n+1) when n is sufficiently large, and it only holds when G is the complete bipartite graph K_{n,n+1} . Let \mathcal{M} be the set of missing edges in G . Then we have that |\mathcal{M}|=\binom{2n+1}{2}-e(G)\leq n^{2}. (1) For convenience, let \mathcal{M}[S] be the set of missing edges in G[S] and \mathcal{M}[S_{1},S_{2}] be the set of missing edges in G[S_{1},S_{2}] . Let \Delta be the maximum degree of G . Since the degree of each vertex in G lies in \{0,1,\dots,2n\} , and |V(G)|=2n+1 , by the pigeonhole principle, there exist two vertices with the same degree. Let \beta be the largest integer such that there exist at least two vertices with degree \beta . Let S be the sum of degrees of all vertices in G . Then S=\sum_{v\in V}d(v)=2e(G)\geq 2n^{2}+2n. (2) We will consider two cases when \beta>n and \beta\leq n , which are solved in Sections 3 and 4 , respectively. From now on, we always assume that n\geq f(\ell) for some large polynomial function f(\ell) of \ell . 3 Proof of Theorem 1.3 in the \beta>n case Recall that G is a graph on 2n+1 vertices with at least n^{2}+n edges, such that no two vertices with the same degree are connected by a P_{2\ell+2} , where P_{k} is the path on k vertices. We need the Erdős-Gallai theorem as follows. Theorem 3.1 (Erdős and Gallai [ 3 ] ) Let G be a P_{k} -free graph on n vertices, then e(G)\leq\frac{(k-2)n}{2} . Let u_{1} and u_{2} be the two vertices with degree \beta in G . Let \alpha=\mathbf{1}_{u_{1}u_{2}\in E(G)} , that is, \alpha=1 if u_{1}u_{2}\in E(G) , and \alpha=0 otherwise. Let c=\beta-n-\alpha . Then we have c\geq 0 . Define \displaystyle B_{12} \displaystyle=N(u_{1})\cap N(u_{2}), \displaystyle B_{1} \displaystyle=N(u_{1})\setminus N[u_{2}], \displaystyle B_{2} \displaystyle=N(u_{2})\setminus N[u_{1}], and B=B_{1}\cup B_{2}\cup B_{12} , D=V(G)\setminus(B\cup\{u_{1},u_{2}\}) . From now on, we always use the corresponding lower case letters to denote the size of each set. For example, b_{i}=|B_{i}|,d=|D| and |B_{12}|=b_{12} . Note that N(u_{i})\setminus\{u_{i+1}\}=B_{i}\cup B_{12} for i=1,2 , where the subscript modulo 2. Thus \beta-\alpha=b_{1}+b_{12}=b_{2}+b_{12} . Moreover, we have \displaystyle b=2(\beta-\alpha)-b_{12}=2n+2c-b_{12}=2n-1-d, (3) \displaystyle d=2n-1-b=b_{12}-2c-1, \displaystyle b_{1}=b_{2}=\beta-\alpha-b_{12}=c+n-b_{12}=n-c-1-d. By ( 3 ), b_{1}=b_{2}\leq n . Note that G[B_{12}] is P_{2\ell} -free; otherwise, there is a path with length 2\ell+1 connecting u_{1} and u_{2} . Thus, e(G[B_{12}])\leq 2\ell n by Theorem 3.1 . Similarly, G[B_{1},B_{12}] , G[B_{2},B_{12}] and G[B_{1},B_{2}] are P_{2\ell} -free, and each of them has at most 2\ell n edges. Then, e(G[B_{12}])+e(G[B_{1},B_{12}])+e(G[B_{2},B_{12}])+e(G[B_{1},B_{2}])\leq 8\ell n . Claim 3.2 d>n^{0.9} . Proof. Suppose otherwise d\leq n^{0.9} . Then we have \displaystyle n^{2}+n\leq e(G) \displaystyle\leq 2\beta+e(G[B_{1}])+e(G[B_{2}])+e(G[B_{12}])+e(G[B_{1},B_{12}]) (4) \displaystyle+e(G[B_{2},B_{12}])+e(G[B_{1},B_{2}])+e(G[D])+e(G[B,D]) \displaystyle\leq 2\beta+e(G[B_{1}])+e(G[B_{2}])+8\ell n+e(G[D])+e(G[B,D]) \displaystyle\leq 2\beta+\binom{b_{1}}{2}+\binom{b_{2}}{2}+3n^{1.9}-|\mathcal{M}[B_{1}]|-|\mathcal{M}[B_{2}]|. The last inequality holds because e(G[D])+e(G[B,D])+8\ell n\leq 2nd+8\ell n\leq 3n^{1.9} since d\leq n^{0.9} and n is large enough. Note that b_{1}=b_{2}=\beta-\alpha-b_{12} . Then ( 4 ) implies that b_{1}=b_{2}\geq n-n^{0.95} , otherwise we have a contradiction when n is sufficiently large. Define \tilde{B}_{i}=\{v\in B_{i}\mid d(v)\geq 1.1n\},i=1,2. Then e(G[B_{1},V\setminus B_{1}])\leq b_{1}+e(G[B_{1},B_{12}])+e(G[B_{1},B_{2}])+e(G[B_{1},D])\leq 3n^{1.9} . Note that each vertex in \tilde{B}_{1} corresponds to at least 0.1n edges in G[B_{1},V\setminus B_{1}] , then |\tilde{B}_{1}|\leq 30n^{0.9} . Similarly, we