Recent searches
Search options
The other day I was thinking about graphs that have degree sequence 1,3,3,3,... such graphs can't be bipartite, so I was wondering whether it is possible for such a graph to have no even cycle. It turns out that graphs with no even cycle have at most (3n-3)/2 edges (I think), whereas my graphs have exactly (3n-2)/2 edges!
Easy proof: A graph with no even cycle must be a cactus, or else by ear decomposition of blocks it would have a theta (three disjoint paths between two endpoints), and two of the three paths would form an even cycle. Cactuses are formed from one vertex by repeatedly gluing new cycles or edges at one vertex. The one-vertex graph obeys your formula, each glued edge adds one vertex and edge, and each cycle adds one more edge than vertices, so the bound on edges follows by induction. #proofinatoot
@11011110 oh that's great! The proof I had in mind (I think I saw it on MO) had to do with spanning trees I think... for contradiction assume you can put more than (n-1)/2 edges back in.But each edge is in exactly one cycle (else a theta) and if that cycle is C₅ then it might as well be two C₃'s (maybe assume maximum counter example). But each triangle uses up two tree edges, so there can be at most (n-1)/2 of them... #proofinatoot (I think)
@11011110 probably SE not MO I guess as it's an exercise really.
I like your proof better especially as it hadn't occurred to me that such a graph should be a cactus!