Question

یال های یک گراف کامل n راسی به تعدادی دور با طول ۳ افراز شده است ثابت کنید یا n-1 یا n-3. بر ۶ بخشپذیر است

Answer 1

راس دلخواه $V_1$ را در نظر بگیرید. این راس در دور هایی حضور دارد که با توجه به تعریف افراز، دوبه‌دو هیچ اشتراکی در یال هایشان نیست. از طرفی درجه هر راس در یک دور برابر $2$ است؛ بنابراین درجه راس $V_1$ عددی زوج است. همچنین می‌دانیم گراف کامل و از مرتبه $n$ بوده و درجه هر راس در آن برابر $n-1$ می‌باشد. نتیجه می‌گیریم $n-1$ عددی زوج و $n$ عددی فرد است.

در هر گراف کامل با $n$ راس داریم :

$n(n-1)=2q$

از آنجا که یال ها به زیرمجموعه های سه تایی افراز شده اند، پس $q$ مضرب $3$ است؛ بنابراین:

$3|q\Rightarrow 3|2q \Rightarrow 3|n(n-1)$ $\Rightarrow 3|n \ \vee 3|n-1$

در حالت اول $(3|n)$ می‌دانیم $n$ عددی فرد و مضرب $3$ است؛ پس $n-3$ عددی زوج و مضرب $3$ است یا به عبارت دیگر:

$6|n-3$

در حالت دوم $(3|n-1)$ می‌دانیم $n-1$ عددی زوج و مضرب $3$ است یا به عبارت دیگر:

$6|n-1$