Paths from cycles

Exercise from Diestel. Let G be a graph and let C be a cycle in G. Let u,v\in C. Let P be a path from u to v of length (i.e. number of edges) equal to k . Then there exists a path in G of length \geq \sqrt{k}.

Proof. Wlog |C|<\sqrt{k}, otherwise we are done. Let P\cap C :=\{v_0, \ldots, v_n\} and n < \sqrt{k}. Let P_i:=v_i P v_{i+1} for every 0\leq i\leq n-1 and let m:=max_{i} \{|P_i|\}. Then k=\sum_{i=0}^{n} |P_i| \leq \sum_{i=0}^{n} m = mn < m\sqrt{k} , hence m>\sqrt{k}. Let j be such that |P_j|=m, then v_j P v_{j+1} C v_j is a cycle of length l\geq m+1 > \sqrt{k}+1.Q.E.D..

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s