Let G = (V, E) be an undirected, unweighted graph with the following prop- erty: for...

 

Transcribed Image Text:

Let G = (V, E) be an undirected, unweighted graph with the following prop- erty: for every vertex v € G, we have that degree(v) ≥ 100 V1/5. That is, every vertex v has at least 100|V1/5 neighbors. The Problem: prove that the graph G above contains a cycle with at most 10 edges. HINT: pick an arbitrary vertex s and consider doing a BFS from s. How do you know when you have found a cycle using BFS? How can you use the fact that every vertex has high degree to prove that you will find a cycle within a small number of BFS layers, and so the cycle must contain few edges? I'm being a bit vague on purpose; these are meant to be hints that point you in the right direction, but I leave it to you to figure out the details. GRADING NOTE: You don't need a proof by induction or anything like that. By "prove" I just mean a detailed justification that would fully convince someone who is seeing this problem for the first time. Let G = (V, E) be an undirected, unweighted graph with the following prop- erty: for every vertex v € G, we have that degree(v) ≥ 100 V1/5. That is, every vertex v has at least 100|V1/5 neighbors. The Problem: prove that the graph G above contains a cycle with at most 10 edges. HINT: pick an arbitrary vertex s and consider doing a BFS from s. How do you know when you have found a cycle using BFS? How can you use the fact that every vertex has high degree to prove that you will find a cycle within a small number of BFS layers, and so the cycle must contain few edges? I'm being a bit vague on purpose; these are meant to be hints that point you in the right direction, but I leave it to you to figure out the details. GRADING NOTE: You don't need a proof by induction or anything like that. By "prove" I just mean a detailed justification that would fully convince someone who is seeing this problem for the first time.