Study On The Gallai Conjecture For A Special Class Of Graphs Of Order Eight

In this thesis,we study a problem about path decompositions of graphs.Gallai proposed the path decomposition conjecture on graphs in 1966.The content of this conjecture is: Every simple connected graph on n vertices can be decomposed into at most ?n/2? paths.This conjecture has not been completely resolved since it was proposed.This thesis proves that Gallai's conjecture is ture for simple connected graphs of order 8,with minimum degree 3 and maximum degree 4.