So I have one question about defining the type of graph I was working on: Define A Graph - Tree Graph With "Cycles" as Nodes
A short summary for the graph I would like to define as G=(V,E):
Definition 1: A tree with nodes as cycles is connected, loop-less graph (no multiple edges) in which every vertex is part of at most one cycle.
This means the cycles have disjoint sets of vertices in the graph. Here I also want to have another definition of an cycle-connected vertex:
Definition 2: A cycle-connected vertex v is a vertex that has degree larger than 2 and belongs to a particular cycle C. Furthermore, there must exist a unique path from v to another cycle in G such that the path does not contain any vertex of the cycle v belongs to.
For the question, I would like to prove this theorem by induction proof:
Given a graph G=(V,E) described above with k cycles in the graph where k is larger than 1. There must be at least two cycles that have only one cycle-connected vertex.
Thoughts: If I am correct, It seems like we can prefer to these cycles as a "cycle-leaf" in a tree. So we can say that there exists at least two "cycle-leaves" the the type of graph we defined for any k larger than 1.
Proofs
1. Base case: If k=2, then we have only two cycles connected to each other. By definition 2, we have that each cycle has one cycle connected vertex. Thus, the base case holds.
2. I assume that for k=n, we have at least two cycles that have only one cycle connected vertex. I prefer these two cycles as "cycle-leaves".
3. I assume now for k=n+1, we have two ways to add one more cycle:
_ Connecting the new cycle to one of the cycle-leaves, then the newly added cycle will become a leaf. Thus we still have at least two cycle-leaves.
_ Connecting to another cycle which is not the two cycle-leaves, then we can still guarantee to have two cycle-leaves that are left untouched. We conclude that the case k=n+1 also holds. So the theorem is proved.
Do you think this is sufficient or am I missing something?