1

Given a graph G, can it be split into 2 sets of graphs($ G_1, \; G_2 $) such that, $G_1$ consists only trees and $G_2$ consists only circuits ?

In other words: Is it possible to construct any graph using only circuits and trees ? And if so, what are some examples to the contrary ?

lapin
  • 459
  • I assume you mean that the trees in $G_1$ are vertex disjoint (thus we may say $G_1$ is a forest) and that the cycles in $G_2$ are also vertex disjoint. Also, while $G_1$ and $G_2$ are edge disjoint, I suspect they need not be vertex disjoint. – hardmath Oct 18 '15 at 14:54
  • @hardmath. Yes, I completely agree with you. So is it possible ? – lapin Oct 18 '15 at 15:05
  • If you require that the cycles in $G_2$ are vertex disjoint, then an example of "impossiblity" is the bowtie graph, two triangles joined at a vertex. If we remove one of the triangles, what remains is connected but not cycle-free. – hardmath Oct 18 '15 at 15:07
  • Alternatively you may be distinguishing circuits and cycles by allowing repeated vertices in a circuit, in which case the bowtie graph is not a counterexample because it is a circuit. – hardmath Oct 18 '15 at 15:16
  • @hardmath I did fail to distinguish between the two. If $G_2$ has circuits(vertices can be repeated) then bowtie graph is not an example and if $G_2$ has cycles then the cycles have to be edge-disjoint and not vertex disjoint. in the latter case what could be a counterexample ? – lapin Oct 18 '15 at 15:29
  • There is no counterexample if $G_2$ consists of "circuits". You can simply remove cycles from $G$ and combine them with pre-existing circuits in (work-in-progress) $G_2$, until no more cycles are present. What remains is your $G_1$, a forest. – hardmath Oct 18 '15 at 15:33

1 Answers1

1

An important distinction to draw is that circuits are closed trails (repeated vertices allowed within a trail) and that cycles are closed simple paths (no repeated vertices allowed).

Then it is possible to decompose (an undirected finite graph) $G$ into edge disjoint subgraphs $G_1$ which is a vertex disjoint collection of trees (a forest) and $G_2$ which is a vertex disjoint collection of circuits.

One way to proceed is by a method of descent (induction). If $G$ does not contain a cycle, then it is a forest and we are done ($G_1 = G$ and $G_2 = \emptyset$).

As long as $G$ does contain a cycle, say $C$, remove those edges and any vertices otherwise isolated in $G$ to get $G\backslash C$. By induction hypothesis $G\backslash C$ can be decomposed into a forest $G_1$ and a collection of vertex disjoint circuits $G_2$. If $C$ is vertex disjoint from all the circuits in $G_2$, then simply adjoin $G_2 \cup C$ to the existing collection of circuits.

Otherwise $C$ will share vertices but not edges with (finitely many) circuits in $G_2$. Travelling around $C$ we introduce loops through these existing (vertex disjoint) circuits to build a larger circuit, at each node of $C$ that is shared with (at most one) circuit of $G_2$. The resulting enlarged circuit is then vertex disjoint from all circuits in $G_2$ that did not intersect $C$.

hardmath
  • 37,015