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 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$?2012-08-12
  • 0
    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.2012-08-12
  • 0
    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$.2012-08-12
  • 0
    Sorry, I forgot to add that it's for a graph G with n vertices where n > 2.2012-08-12
  • 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
    hmm..true. I've updated the definition of a club in the question above. Sorry about leaving out a detail.2012-08-12
  • 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