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