در گراف کیلی،
Cay(G,S)
چه راسهایی دارای همسایه مشترک هستند؟
می دانیم که رئوس در گراف کیلی اعضای گروه
G
هستند. عمل گروه را ضرب بنامیم. همچنین اتصالات در گراف کیلی بدین صورت است:
$ \forall x,y \in G, x \sim y \Leftrightarrow y ^{-1}x \in S.$
راس
$y$
را در نظر می گیریم. می خواهیم رئوسی را بیابیم که در این راس همسایگی مشترک دارند، یعنی رئوسی که وصل به
$y$
هستند. با استفاده از تعریف داریم:
$x \sim y \Leftrightarrow y ^{-1}x \in S$
$ y ^{-1}x = s \rightarrow x=ys \rightarrow xs^{-1}=y$
$y \sim z \rightarrow z^{-1}y \in S$
$z^{-1}y=s^{'} \rightarrow z^{-1}xs^{-1}=s^{'} \rightarrow z^{-1}x = s^{'}s$
می توان نتیجه گرفت که دو راس در گراف کیلی همسایه مشترک دارند اگر و فقط اگر
$s , s^{'}$
ای با شرایط بالا در
$S$
موجود باشند که وارون یکی ضرب در دیگری با حاصل ضرب
$s , s^{'}$
برابر شود؟
