设$G$是具有$n$个顶点的简单连通图。Gallai于1966年提出关于图的路分解猜想: 每个$n$阶简单连通图$G$都可以被分解为至多$\left\lceil\frac{n}{2}\right\rceil$条路。在本文中, 我们利用算法证明了Gallai猜想对于完全二部图$K_{n_1, n_2}$成立, 这里1≤n₂ < n₁且n₁是奇数。结合Constantinou和Ellinas (2018)的结果, 我们证明了对于任意的完全二部图, Gallai猜想成立。

Let $G$ be a connected simple graph on $n$ vertices. The Gallai's conjecture (1966) asserts that every simple connected graph $G$ on $n$ vertices can be decomposed into at most $\left\lceil\frac{n}{2}\right\rceil$ paths. In this paper, we prove that Gallai's conjecture is true for each complete bipartite graph $K_{n_1, n_2}, $ where 1≤n₂ < n₁ and n₁ is odd. Together with the conclusions of [1], we show that Gallai's conjecture holds for all complete bipartite graphs.