اول اینکه باید بگیم k > 1 چون در غیر اینصورت مثال نقض وجود داره . ( دو مثلث را در نظر بگیرید که یک راس مشترک دارند )

حالا برهان خلف میزنیم . دو راس u و v داریم که k همسایه مشترک دارند و مجموعه های B و A به ترتیب مجموعه رئوس مجاور با u که با v اشتراک ندارند و A هم قرینه ی B , مجموعه K هم همون k راس مشترکن . (البته بی شکل هم میشد گفت ولی اینجوری فهمش آسونتره)
فرض اولیه » تعداد رئوس A با تعداد رئوس B برابر نیست ( اگر در این مورد به تناقض برسیم سوال حله ) بعد میایم راس w از A رو در نظر میگیریم .
میدونیم این راس k تا همسایه مشترک با V داره . مثلن x تا از اونها عضو K و k - x تا از اونا عضو A هستند . خب میدونیم w با U هم k تا همسایه مشترک داره از طرفی میدونستیم که x ، w تا یال به مجموعه K داره پس نتیجه میگیریم که k - x تا یال هم به مجموعه B داره .

نتیجه 1 » خب حالا میشه نتیجه گرفت که درجه هر راس در داخل A برابره با تعداد یالهایی که به مجموعه B داره . ( منظور از درجه داخلی در A یعنی یالهایی که به بیرون از A داره محاسبه نمیشن ) این نتیجه برای مجموعه B هم وجود داره ( چون شکل متقارنه و این حرفا)

نتیجه 2 » از نتیجه 1 میشه نتیجه گرفت که تعداد یالهای بین A و B دو برابر تعداد یالهای داخل A هست چون هر یال که دو سرش در داخل مجموعه A هست در واقع هر بار توسط هر یک از دو سرش محاسبه شده و بین A و B آمده ( این خیلی واضحه ! ) خب از اینرو میشه نتیجه گرفت تعداد یالهای داخل A با تعداد یالهای داخل B برابره

نتیجه 3 » میدونیم تعداد یالهای بین دو مجموعه A و K برابره با تعداد یالهای بین دو مجموعه B و K . ( چرا ؟ با استفاده از نتیجه 2 و اینکه درجه هر راس در A و K برابره با k و برای B هم همینطور ) از طرفی میدونستیم

درجه هر راس در داخل A ( و به قرینه ی اون در داخل B ) + تعداد یالهای اون راس به مجموعه k = K

پس در این صورت تعداد راس ها رو میشه بر حسب یالها شمرد ( دو برابر یالها تقسیم بر k = تعداد رئوس). چون یالها در A و B برابره پس راس ها هم برابر حساب میشه پس نتیجه میگیریم که تعداد رئوس در A و B برابره . که با فرض اولیه مون تناقض داره .

فرض کنید هر دو راس $k$ تا همسایه ی مشترک داشته باشند .

بدیهی است که گراف دور فرد دارد . پس گراف دو بخشی نیست .

حال راس $v$ را در نظر بگیرید . مجموعه ی همسایه های $v$ را $A$ می نامیم و مجموعه ی راسهای غیر مجاور با $v$ را $C$ می نامیم .

تعداد یالهای بین $A$ و $C$ را به دو روش می شماریم . و در نتیجه برای راس دلخواه $u$ که در $A$ است داریم

$(n-d_v -1) k = d_v (d_u -1 -k)$

با استفاده از این داریم $d_u = \frac{k(n-1)}{d_v} + 1 $

چون به ازای هر راس دلخواه u در A‌ درجه ی آن برابر است با مقداری که در بالا گفته شده ، پس درجه ی همه ی رئوس A همین مقدار است و با هم برابر هستند . پس به ازای هر راس v در گراف درجه ی تمام راسهای مجاور با $v$ یکسان است .

با توجه به اینکه در این گراف دور فرد داریم می توان به راحتی ثابت کرد که از هر راس به خودش یک گشت بسته ی به طول فرد وجود دارد . و با استفاده از این می توان ثابت کرد که درجه ی هر راس با درجه ی راسهای مجاورش یکسان است .

توضیح بیشتر : یک دور فرد به طول 2k+1 را در نظر بگیرید . می دانیم درجه ی همسایه های هر راس در این دور یکسان است . پس درجه ی راس 1 با درجه ی راس 3 و ... با درجه ی راس 2k+1 یکسان است . اما درجه ی راس 2k+1 و راس 2 با هم یکسان است . پس درجه ی راس یک با درجه ی راس دو یکسان است . به همین روش ثابت می شود درجه ی هر دو راسی که در یک گشت بسته ی فرد قرار دارند یکسان است .

(قسمت هایی از اثبات رو حوصله نداشتم دقیق بنویسم اگر براتون واضح نبود بگید که دقیق توضیح بدم . (خواهشا نگید!!!) )