most recent 30 from http://mathoverflow.net 2013-06-19T14:41:18Z http://mathoverflow.net/feeds/question/30759 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/30759/in-a-graph-is-it-always-possible-to-construct-a-set-of-cycle-bases-with-each-an Graviton 2010-07-06T11:34:37Z 2010-07-06T13:03:33Z

<p>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?</p> <p>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. </p>

http://mathoverflow.net/questions/30759/in-a-graph-is-it-always-possible-to-construct-a-set-of-cycle-bases-with-each-an/30767#30767 Thorny 2010-07-06T12:38:13Z 2010-07-06T12:38:13Z

<p>Consider the complete graph on 7 vertices. It has 21 edges, so any set of cycles that utilizes each edge at most twice has size at most 42/3=14. But the cycle space of the graph has dimension 21-7+1=15, so you cannot have a basis with the requested property.</p>