Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
add comment

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

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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