Given a graph G(V,E) on n vertices, an edge-partition of the edge set, E, is a set of subsets, Ei. The set {Ei} covers G if every edge of G is contained in one of the Ei's. In 1959, Erdos and Gallai conjectured that the number of disjoint paths and cycles that could cover any connected graph of n vertices is at most [(n+1)/2]. In this thesis, we present a summary of known results related to coverings of graphs and an introduction to the probabilistic method. We will use the probabilistic method to try to prove that the conjecture is true for connected graphs and that our upper bound is the best possible.
展开▼
