Node degree and the size of disconnected subgraphs

Node degree and the size of disconnected subgraphs

Theorem For a graph of $N$ nodes,we have,with $m \geq 0$ and $k \geq 1$ ,

(0) $N > \left( {m + 1}\right) \cdot \left( {k - 1}\right) \Rightarrow P \vee Q\;$ ,where

$P \equiv$ (there exists a node connected to more than $m$ other nodes)

$Q \equiv$ (there exists a subset of $k$ mutually disconnected nodes).

The given lower bound for $N$ is sharp. (End of Theorem.)

Proof. The sharpness is demonstrated by constructing a graph with $N = \left( {m + 1}\right) \cdot \left( {k - 1}\right)$ ,for which $P \cap Q$ holds, viz. $k - 1$ copies of the complete(m+1)-graph.

Each node being connected to m other nodes, we have nP.

Each subset of $k$ nodes containing a pair belonging to one of the $k-1$ complete graphs, we have $7^k$ .

The sufficiency of the lower bound shown by mathe-matical induction over $k$ , more precisely the base for $k = 1 \lor k = 2$ , and the step from $k$ to $k + 2$ .

[{B}_{a1} = 1]

$$ N > (m + 1) \cdot (1 - i) $$

$$ = {\mathrm {a r i t h m e t i c} } $$

$$ N > 0 $$

$\Rightarrow {a$ subse) of 1 node contains no connected pair} Q(k:=1) $\Rightarrow { P$ does not depend on $k}$

$$ (P \vee Q) (k = 1) $$

$$ \begin{array}{l} k = 2 \ N > (m + 1) \cdot (2 - 1) \ = {\mathrm {a r i t h m e t i c} } \ N - 1 > m \geq 0 \ \Rightarrow {a \mathrm {n o d e i s c o n n e c t e d t o} N - 1 \mathrm {o t h e r s o r t o f e w e r} } \ \begin{array}{r l} & {= {\mathcal {P} \mathrm {d o e s n o t d e p a n d o n} k }} \ & {\quad (\mathcal {P} \vee Q) (k := 2)} \end{array} \ \end{array} $$

Step Using (0) we shall show $Q(k := k + 2)$ under the assumption $N > (m + 1) \cdot (k + 1) \land \neg P$ by constructing a subset of $k + 2$ mutually disconnected nodes.

Under the assumption, there is a disconnected pair, $(X,Y)$ say; because of $\neg P$ , of the other $N - 2$ nodes, at most 2-m nodes are connected to $X$ or to $Y$ , hence at least $N - (m + 1)\cdot 2$ , i.e. more than $(m + 1)\cdot (k - 1)$ , of those other nodes are connected to neither $X$ nor $Y$ . From (0) we conclude among them a subset of $k$ mutually disconnected nodes; together with $X$ and $Y$ this yields a subset of $k + 2$ mutually disconnected nodes, hence $Q(k := k + 2)$ .

(End of Proof.)

Austin, 11 June 1986

prop. dr. Edsger W. Dyrksta Department of Computer Sciences The University of Texas at Austin Austin, TX 78712-1188

USA