2
$\begingroup$

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.

  • 0
    What about the graph o--o--o--o with $n=4$?2012-08-12

1 Answers 1

1

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

  • 0
    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.2012-08-20