利用Hall定理证明并推广Hakimi定理

Prove and Generalize Hakimi’s Theorem Using Hall’s Theorem

摘要: 图的荫度理论一直是图论中主要的研究问题，Nash-Williams定理给出了图的荫度至多为k的充要条件，对应的，Hakimi定理给出了图的伪荫度至多为k的充要条件，本文主要是利用Hall定理，给出了证明Hakimi定理的一个新思路，并利用同样的思路将Hakimi定理推广至了分数形式。

Abstract: The theory of graph arboricity has always been a primary research topic in graph theory. Nash-Williams’ theorem provides the necessary and sufficient conditions for a graph to have an arboricity at most k, while Hakimi’s theorem gives the corresponding conditions for a graph to have a pseudo-arboricity at most k. This paper primarily employs Hall’s theorem to present a novel approach for proving Hakimi’s theorem and further extends Hakimi’s theorem to a fractional form using the same reasoning.