I'm new to proofs and I'm trying to prove the one in the title for an undirected graph. However, I'm very restricted to the methods I can use. I was given the definition of a $cycle$, a $path$ and a $connected$ $component$ and I may or may not use these facts without further proof:
- If a node $v$ has a path to another node $u$, then $\deg(v) > 0$ and $\deg(u) > 0$.
- $\sum_{v \in V} \deg(v) = 2|E|$
This means I cannot use other terms like e.g., "tree" or facts about trees. I've spent a few days now on this problem. I tried to reformulate ideas from similar proofs like this one or use strategies like the one in this youtube video. All my previous solutions have not been convincing so far or I got stuck somewhere.
Any help would be appreciated.
Can you show that a cycle of $k$ vertices has $k$ edges?
If so, start by supposing there is a cycle of $k$ vertices and observe that the remaining $n - k$ vertices each need to be connected to the cycle. How many edges does that imply?