0

Suppose a graph has n vertices and k edges, for n ≥ 1. Prove that the number of cycles in the graph is at least $k − n + 1$.

I started doing induction on the number of edges and got stuck;

base case: k=0 then number of cycles is atleast $-n+1≤ 0$

suppose it holds for k=x, that is number of cycles it atlas $x-n+1$ then want to show it holds for $k=x+1$, so want to show the number of cycles is atleast $x+1+n+1$=$x-n+2$ and this is where I get stuck finishing the proof.

user520403
  • 459
  • 1
    What have you tried? What are your thoughts on this? What results from graph theory do you know that seem like they could be relevant? – Arthur Oct 14 '20 at 22:56
  • It is not an appropriate behaviour to post a question without leaving a comment. Especially if heropup has made great effort to answer your question. – callculus42 Oct 18 '20 at 19:46

0 Answers0