An upper bound for cut cover size of a graph

We start by familiarizing ourselves with edge covers. We review several\ud interesting results for covers using triangles and covers using cycles. We then\ud consider covering a graph with cuts.\ud Determining the minimum total number of edges in a cut cover of a graph,\ud called its cut cover size, is an NP-complete problem. We investigate some\ud special cases of graphs for which the cut cover size can be easily determined.\ud The main result of this thesis is that the cut cover size of a graph is bounded\ud from above by 2e - n + 1 when the graph is connected and has e edges and\ud n vertices.\ud Before proving the main result, we look at specific cases where the bound\ud holds with equality, namely in trees, odd cycles and most complete graphs.\ud We then make a key observation that the main result is related to a known\ud upper bound using the maximum size of a stable cut. This observation gives\ud us a simpler inequality to consider. We prove the main result by proving the\ud simpler inequality by induction. Finally, we prove that equality holds in the\ud bound precisely for those connected graphs all of whose blocks are complete\ud graphs Kn(n =I- 4,8) or odd cycles e2k+!