1
$\begingroup$

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.

$\endgroup$
6

1 Answer 1

5
$\begingroup$

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.

$\endgroup$
9
  • $\begingroup$ I don't follow your logic, is there any nonintuitive properties of graphs and edges that you make use of when you make this deduction? $\endgroup$
    – Graviton
    Jul 7, 2010 at 7:01
  • $\begingroup$ I implicitly use that all cycles contain at least 3 edges, and that the dimension of the cycle space is the number of edges exceeding that of a tree with the same vertices. Both facts are straightforward, could you please elaborate on where exactly you have problems? $\endgroup$
    – Thorny
    Jul 7, 2010 at 9:44
  • $\begingroup$ Thorny, first are you saying that you assume a graph with 7 vertices and 21 edges? If yes, then your reasoning at most hold for that case, what about other case? Second, how do you actually define dimension of the cycle base? $\endgroup$
    – Graviton
    Jul 7, 2010 at 12:49
  • 1
    $\begingroup$ I answer the question "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?" in the negative, so one counterexample is all it takes. If you wanted to ask a more precise question, then BS's lead is what you should read. As for your other question, please consult en.wikipedia.org/wiki/Cycle_space . $\endgroup$
    – Thorny
    Jul 8, 2010 at 7:21
  • $\begingroup$ @Thorny, I still don't quite follow your logic. If you may, you might want to construct a diagram that answers my question negatively in graphical terms, that would be tremendously helpful. Sorry and thanks a lot! $\endgroup$
    – Graviton
    Jul 13, 2010 at 14:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.