A cut in a graph G is the set of all edges between some set of vertices S and its complement V(G)-S. A cut-cover of G is a collection of cuts whose union is the edge-set E(G) and the total size of a cut-cover is the sum of the number of edges of the cuts in the cover. The cut-cover size of a graph G, denoted by cs(G), is the minimum total size of a cut-cover of G.We will give general bounds on cs(G), find sharp bounds for classes of graphs such as 4-colorable graphs and random graphs and prove a Nordhaus-Gaddum type result. We close with a list of open problems.