Assume n is even. Considering a graph where each vertex in $v_1,...,v_n$ is adjacent to the next (ie $v_i \sim v_{i+1}$ for $1\leq i<n$) and where $v_1,v_n$ are each connected to at least $n/2$ other edges, show there is always an $i$ such that $v_{i+1} \sim v_1$ and $v_i \sim v_n$. (Here using the notation $\sim$ to mean adjacent to.)

I'm not sure the best way to show this. I considered using induction, but after proving the base case for $n=2$, I wasn't sure how to do the induction step. Is saying something along the lines of "Assume true for $k<n$. Connect $v_1$ and $v_n$ to the same numbered vertices (ie. connect to $v_j$ for the same $j$) as in the graph with $n-2$ (the next lowest case since we are assuming n even) and then add an additional edge from each of $v_1,v_n$. By induction the same vertices $v_i,v_{i+1}$ will exist as in the $n-2 $ case such that the theorem is true" sufficient? It seems too sloppy.

I also considered somehow using the pigeonhole principle. Since each vertex $v_1,v_n$ can reach a maximum of $n-2$ vertices with its additional $n/2$ (since it is automatically such that $v_1 \sim v_2$ and $v_n \sim v_{n-1}$), the pigeonhole principle shows that both vertices $v_1,v_n$ must be adjacent to at least 2 of the same vertices. However I'm not sure how I can show that these are next to each other, if indeed they are.

Is there another way of proving this I am not thinking of? What method would work best?

  • $\begingroup$ When you say $v_1,v_n$ are each connected to $n/2$ other edges, do you mean that the total degree of $v_1,v_n$ is $n/2$ or $n/2+1$? I.e. are you counting $v_1\tilde v_2$ in your $n/2$ count. $\endgroup$ – Alex R. Mar 2 '15 at 6:52
  • $\begingroup$ I am not counting $v_1 \sim v_2$, so the total degree of $v_1$ is $n/2 +1$ $\endgroup$ – AccioHogwarts Mar 2 '15 at 7:08

Consider the path $v_1$ to $v_n$; degree of $v_1$ and $v_n$ is at least $n/2+1$. Suppose the neighbors of $v_n$ are some $v_i$ for some values of $i$. Consider the vertices $v_{i+1}$, which are at least $n/2+1$ in number. Now applying Pigeonhole you will have a particular $v_k$ satisfying your conditions.

This technique is the basis for most of the problems to prove existence of Hamiltonian cycles.

EDIT: I just saw that you had problem applying Pigeonhole, so I am explaining it a bit more. Among the $n/2+1$ vertices of the type $v_{i+1}$ given above, at least one will be adjacent to $v_1$. Since $v_1$ has degree at least $n/2+1$ (else there should be $> n$ vertices from $v_1$ to $v_n$). (Drawing a figure will make it easy to understand.)

  • $\begingroup$ How does the pigeonhole principle apply in this case? Since the number of values of possible $v_{i+1}$ is the same as the degree of $v_1$ could you not just say choose one? Or would you say that if all vertices adjacent to $v_1$ are those adjacent to $v_n$ then at least one of the i must be adjacent since $(n/2 +1)+(n/2 + 1)=n+2$ and if all the vertices adjacent to $v_1$ are not those adjacent to $v_n$ then at least one must be in the options for $v_{i+1}$? $\endgroup$ – AccioHogwarts Mar 2 '15 at 8:17
  • $\begingroup$ @AccioHogwarts Just edited the answer. If you still have problems please do look into the proof of Dirac's theorem for Hamiltonian graphs (proofwiki.org/wiki/Dirac%27s_Theorem). $\endgroup$ – user67773 Mar 2 '15 at 9:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.