# Best way to prove adjacency of a graph

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?

• 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. – Alex R. Mar 2 '15 at 6:52
• I am not counting $v_1 \sim v_2$, so the total degree of $v_1$ is $n/2 +1$ – AccioHogwarts Mar 2 '15 at 7:08

## 1 Answer

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.)

• 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}$? – AccioHogwarts Mar 2 '15 at 8:17
• @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). – user67773 Mar 2 '15 at 9:56