A graph has minimum degree $17$. Prove that it contains at least $136$ cycles 
A graph $G$ (simple, not oriented) has minimum degree $17$. Prove that
$G$ contains at least $136$ cycles.

Two cycles are the same if their set of edges is the same.
I was thinking this: Choose a random vertex $v_1$, this vertex has at least $17$ edges, let's say, $E_1,E_2,\ldots,E_{17}$. Now choose a random path starting from $E_1$ and ending in $E_2$. Then a random path starting in $E_1$ and ending in $E_3$, then $E_4$,.... and $E_{17}$, that's $16$ cycles in total. I can do the same with $E_2$ and $E_i$ for $i>2$, and with $E_3$ and $E_j$ for $j>3$ etc. That would be $16+15+\ldots+1=136$.
But all of this is under the false assumption that I can get from random $E_i$ to every $E_j$ for $j>i$. So I thought maybe I can prove that there exists a vertex for which this condition is true for the edges relative to that vertex, but Im not sure that's even true. How would I go about solving this?
 A: But your reasoning makes sense.
Let us take a few steps. We can assume that the graph is connected. (why?)


*

*First, let's find a vertex whose deletion gives us a connected
graph.


Let us assume the contrary and there is no such vertex. Then when any vertex is removed, the new graph has several connected components. Choose vertex $w$ so that we obtain a connected component with the smallest number of vertices. Denote this component by $H$.
Let $H$ contains two or more neighbors of $w$.
Let $H, H_1,\ldots,H_s$ be components of $G-w$ and $u,v$ neighbors of $w$ of $H$. The graph $G-x$ is not connected. The component containing $y$ contains also $w$ and all vertices from $H_1,\ldots,H_s$. Consequently, the other components lie in $H$. This contradicts the fact that $H$ is the minimal component of all possible components.
If $H$ contains only one neighbor of $w$. Let it be $v$. Then $H-v$
contains a component of the graph $G-v$. Contradiction.
Another argument for the existence of $v$ such that $G−v$ is connected: take a leaf of a spanning tree of $G$. Thanks Misha Lavrov.
Note. In both proofs of the existence of $v$ only the connectivity of the graph $G$ is needed.



*Now for each pair of edges incident to $v$ we can construct a
cycle.


Let $x,y$ be two neighbors of $v$. Delete the vertex $v$. We get a connected graph $G'$ again. Then there exists a path $P$ in $G'$ connecting $x$ and $y$. We obtain a cycle $vxPyv$ in graph $G$. The cycles are different for different pairs of $x,y$ and $x'y'$. (why?)



*Such cycles will be $\binom{17}{2}=136$.


