# In a graph, is it always possible to construct a set of cycle bases, with each and every edge Is shared by at most 2 cycle bases?

Given a graph with a list of edges, is it possible to always construct a set of cycle bases for those edges, such that each and every edge is shared by at most 2 cycle bases?

The above question assumes that each and every edge must somehow belong to at least one cycle. IN other words, there is no vertex that is connected to one and only one edge.

-
Here's an extensive survey article on cycle bases: math.uga.edu/~caner/09vigre/SurveyCyclebases.pdf – Doug Chatham Jul 6 '10 at 13:54
And it cites a theorem of MacLane (1937) to the effect that a graph has such a cycle basis if and only if it is planar. – BS. Jul 6 '10 at 14:41
@BS, do you have a refernece on that? – Graviton Jul 7 '10 at 7:01
en.wikipedia.org/wiki/Mac_Lane%27s_planarity_criterion says: S. Mac Lane, A combinatorial condition for planar graphs, Fund. Math. 28 (1937), 22–32. – Thorny Jul 7 '10 at 9:46
Additional reference. Available online and shorter than the Mac Lane paper: ams.org/journals/proc/1973-037-02/S0002-9939-1973-0313098-X/… – Doug Chatham Aug 2 '10 at 15:07