# Prove that given any $2$ vertices $v_0,v_1$ of Graph $G$ that is a club, there is a path of length at most $2$ starting in $v_0$ and ending in $v_1$

Definition of a club: Let $G$ be a graph with $n$ vertices where $n > 2$. We call the graph $G$ a club if for all pairs of distinct vertices $u$ and $v$ not connected by an edge, we have $\deg(u)+\deg(v)\ge n$. Ref: Khoussainov,B. , Khoussainova,N. (2012), Lectures on Discrete Mathematics for Computers Science, World Scientific Pg.(83)

My strategy was to prove this using the proof by cases method.

Case 1: Prove for the case when $v_0$ and $v_1$ are connected by an edge, in which case there is clearly a path from $v_0$ to $v_1$, of length $1$, so this case is proven.

Case 2: Prove for the case when $v_0$ and $v_1$ are not connected by an edge. Now, for this case, since the hypothesis is assumed to be true and Graph $G$ is a club,

$$\deg(v_0) + \deg(v_1)\ge n\;.$$

That's all I've got so far, and I'm not sure how to proceed.

-
What is a Graph Club? I can find the following definition on Google: "An $n$-club $N$ of a graph $G$ is a maximal subgraph of $G$ of diameter $n$". But in that case, what is your $n$? – utdiscant Aug 12 '12 at 8:04
Sorry forgot to add the definition. A graph G is a club if, for all pairs of distinct vertices u and v not connected by an edge, we have deg(u)+deg(v)≤n. – rookie_02 Aug 12 '12 at 8:09
That definition can’t be right: every chain graph satisfies $\deg(u)+\deg(v)\le4$ for all $u,v$, but if the chain has at least four vertices, there are vertices that are not joined by a path of length $\le 2$. – Brian M. Scott Aug 12 '12 at 8:16
Sorry, I forgot to add that it's for a graph G with n vertices where n > 2. – rookie_02 Aug 12 '12 at 8:24
What about the graph o--o--o--o with $n=4$? – Brian M. Scott Aug 12 '12 at 8:27

The statement is not true. Consider a path of length 4, where $v_0,v_1$ are the endpoints of the path. There is no path of length at most two from $v_0$ to $v_1$, and the graph is a club by your definition.

Edit: After the definition of club changed

With the new definition, the proof can be made as follows:

Let $G$ be a (simple) graph which is a club.

Assume there is no path of length 1 or 2 from $v_0$ to $v_1$. Let $S_0$ denote the set of vertices joined to $v_0$ by an edge, and let $S_1$ be the set of vertices joined to $S_1$ by an edge. If there is a vertex $x$ which is in both $S_0$ and $S_1$ (that is $x \in S_0 \cap S_1$), then there is a path $v_0,x,v_1$ of length 2 from $v_0$ to $v_1$, so assume there is no vertex in $S_0 \cap S_1$.

We know by the definition of $S_0$ and $S_1$ that $|S_0| = \text{deg}(v_0)$ and $|S_1| = \text{deg}(v_1)$, and since $G$ is a club, $|S_0| + |S_1| = \text{deg}(v_0) + \text{deg}(v_1) \geq n$. Since $S_0$ and $S_1$ have no vertices in common, this means that any of the $n$ vertices is in either $S_0$ or $S_1$. But this is a contradiction since $v_0,v_1$ are in none of them (if they were, there would be a direct edge from $v_0$ to $v_1$).

-
hmm..true. I've updated the definition of a club in the question above. Sorry about leaving out a detail. – rookie_02 Aug 12 '12 at 8:29
If you are satisfied with the answer, you should mark it as correct. If you are not, you should edit your question or write a comment. – utdiscant Aug 20 '12 at 12:08