Let $G$ be a graph. Let $k$ be the minimal degree of $G$. Show that $G$ contains a cycle of length $k + 1$.
Asked
Active
Viewed 596 times
0
-
At least $k+1$ right? – Asinomás Dec 08 '15 at 23:34
-
It doesn't specify that. It just asked for a length of k+1 – user297125 Dec 08 '15 at 23:36
-
in that case it is false – Asinomás Dec 08 '15 at 23:44
-
Okay -- choose the subgraph on $m$ vertices such that every vertex in the subgraph has degree $v$ then you can use the fact that every $k$-regular graph has a hamiltonian cycle proved by Nash-Williams – user2879934 Dec 08 '15 at 23:44
-
consider $K_{2,2}$ it has no $3$-cycle as it is bipartite – Asinomás Dec 08 '15 at 23:45
-
If I follow the procedure of the similar qs that you posted, what would i have to modify to take in account the different criteria for k? – user297125 Dec 08 '15 at 23:47
-
What different criteria? – Asinomás Dec 09 '15 at 00:00
-
Would the answer be different if its asking for k>1 or just a minimum of k? – user297125 Dec 09 '15 at 00:01
-
well, when $k=1$ the question makes no sense. – Asinomás Dec 09 '15 at 00:53
-
Ya, my teacher isnt the best – user297125 Dec 09 '15 at 01:33
-
alright ill just follow what they did in the link you posted. Thanks – user297125 Dec 09 '15 at 01:33