\chapter{تعاریف و مفاهیم اولیه}
\thispagestyle{empty}
این پایان‌نامه به مطالعه گروه‌های متناهی با استفاده از نظریه گراف می‌پردازد. به عبارت دقیق‌تر، با هر گروه متناهی یک گراف بنام گراف توانی بهبود یافته گروه، کامل، اویلری و غالب باشد و ساختار گروه را مورد بررسی قرار خواهیم داد. بنابراین در اسن فصل، مطالب و مفاهیم اولیه از نظریه گروه و گراف را گردآوری می‌کنیم که در فصل‌های بعد مورد استفاده قرار خواهد گرفت. 
بحث را با نظریه گروه‌ها شروع می‌کنیم.
\section{نظریه گروه‌های متناهی}
\begin{defi}
فرض کنیم $ X $ زیر مجموعه‌ای از گروه $ G $ باشد. در این صورت اشتراک تمام زیرگروه‌های $ G $ که شامل $ X $ هستند، زیرگروهی از $ G $ است (حداقل خود $ G $ شامل $ X $ است) و آن‌را زیر گروه تولید شده توسط $ X $ می‌نامند و با علامت $ \langle  X\rangle $  نشان می‌دهند.
به عبارت دیگر، $ \langle  X\rangle $ کوچکترین زیرگروه $ G $  است که شامل  $ X $ می‌باشد.
\end{defi}
\paragraph*{}
فرض کنیم $ G $ گروه است و  $ g\in G $، زیر مجموعه   $ \langle X\rangle =\{g^{n} \vert n\in \mathbb{Z}$ زیرگروه $ G $  است، این زیرگروه را زیرگروه دوری تولید شده توسط $ g $  می‌نامیم. اگر به ازای عددی چون  داشته باشیم  ، آن‌گاه    متناهی است. در این حالت، اگر کوچکترین عدد صحیح  و مثبتی باشد که   آن‌گاه مساوی تعداد اعضای   است. در واقع  .   را مرتبه عضو می‌نامیم و با    نشان می‌دهیم.
\begin{defi}
گروه را دوری می‌نامیم هرگاه موجود باشد که   .
فرض کنیم  . در این صورت   .   براحتی دیده می‌شود که هر دو گروه دوری از مرتبه یکسان یکریخت هستند. از این رو گروه دوری مرتبه  را با  و گاها با   نشان خواهیم داد.
\end{defi}
\begin{defi}
فرض کنیم  یک عدد طبیعی باشد. در این صورت  را تعداد اعداد صحیح مثبت نا بیشتر از  که نسبت به  اول هستند، تعریف می‌کنیم. به عبارت دیگر      ،   را تابع اویلر می‌نامیم. 
\end{defi}
\begin{lemma}
فرض کنیم . در این صورت   

\end{lemma}
\begin{proof}
به مراجعه شود.
\end{proof}
مرتبه هر  عضو از یک گروه را با  نشان خواهیم داد. هم چنین، مجموعه مولدهای گروه دوری را با  نمایش می دهیم. 

\begin{lemma}
فرض کنیم  یک گروه باشد و . در این صورت 
\begin{itemize}
\item[الف) به ازای هر ،  ]
\item ب) 
\item چ)
\end{itemize}

\end{lemma}
\begin{proof}
به   مراجعه کنید.
\end{proof}
\begin{defi}
فرض کنیم یک عدد طبیعی باشد، روی مجموعه اعداد صحیح ، رابطه همنهشتی  را به صورت زیر تعریف می‌کنیم:

رابطه همنهشتی  یک رابطه هم‌ارزی است. مجموعه رده‌های هم‌ارزی به پیمانه  را با نشان می‌دهیم.


\end{defi}

به ازای هر تعریف می‌کنیم:   . به وضوح  یک گروه دوری متناهی از مرتبه است.
\begin{defi}
گروه نابدیهی را ساده می‌نامیم هرگاه تنها زیرگروه‌های نرمال آن  و خود باشند.


\end{defi}
\begin{lemma}
هر گروه ساده آبلی، دوری از مرتبه اول است.
\end{lemma}
\begin{proof}
به   مراجعه کنید.
\end{proof}
\begin{theorem}
هر گروه دوری از هر مرتبه ممکن دارای دقیقا یک زیرگروه است. به عبارت دقیق‌تر، به ازای هر عامل از  مرتبه گروه دوری  ، دقیقا یک زیرگروه از مرتبه موجود است.
\end{theorem}

\begin{proof}
به   مراجعه کنید.
\end{proof}

\begin{defi}
فرض کنیم   و   مجموعه‌ای ناتهی از خودریختی‌های  باشد. می‌گوییم  یک زیرگروه  ناوردای   است هرگاه  به ازای هر    و  ،   که در آن   تصویر   تحت خودریختی است. در صورتی که ،   ناوردا  باشد گوییم  در مشخصه است. به عبارت دیگر، زیرگروه   را مشخصه می‌نامیم هرگاه به ازای هر داشته باشیم . در این حالت می‌نویسیم   .

مرکز گروه همواره یک ریرگروه مشخصه    است. البته  هرزیرگروه  را بطور  منحصربفرد توسط یک خاصیت نظریه گروهی تعریف شده باشد و انتخاب‌های دلخواه یا به نام اعضاء بستگی نداشته باشد، یک زیرگروه مشخصه است.
\end{defi}

\begin{defi}
گروه نابدیهی را مشحصه‌ایی-ساده می‌نامیم هرگاه تنها زیرگروه‌های مشخصه  آن  و خود باشند.


\end{defi}

\begin{lemma}
فرض کنیم گروه متناهی دارای زیرگروه منحصربفرد  از مرتبه باشد. در این صورت  زیرگروه مشخصه است.
\end{lemma}
\begin{proof}
به ازای هر   ،   ،  چون   و  دارای زیرگروه 


منحصر بفرد از مرتبه است، لذا   . بنابراین  زیرگروه    مشخصه   است.

\end{proof}
\begin{defi}
فرض کنید  و  دو گروه   دلخواه باشند. روی مجموعه حاصلضرب دکارتی  
عمل دوتایی به صورت زیرتعریف می‌کنیم:

در این صورت   با عمل   فوق یک گروه  تشکیل می‌دهد که آن را حاصل‌ضرب مستقیم(خارجی)  و   می‌نامند.

\end{defi}
\begin{defi}
زیرگروه جابجاگر گروه   را با نشان می‌دهیم  و به صورت    

تعریف می‌کنیم که در آن    .


\end{defi}


\begin{defi}

گروه  را کامل گوییم هرگاه   . برای مثال، هر گروه ساده غیرآبلی، یک گروه کامل است.
\end{defi}
\begin{defi}
فرض کنیم یک گروه باشد. در این صورت زیرگروه دوری   از را زیرگروه دوری ماکسیمال می‌نامیم هرگاه هیچ زیرگروه دوری به طور سره شامل در  موجود نباشد.


\end{defi}
\begin{lemma}
فرض کنیم    ، در این صورت   .
\end{lemma}
\begin{proof}
فرض کنیم   . اگر    ، آنگاه  برای هر     داریم:  


که  در اینجا . بنابراین  هیچ عنصری چون   نمی‌تواند   را تولید کند که در این یک تناقض است.پس   است.

\end{proof}
\begin{defi}
فرض کنیم  یک گروه باشد و     . در این  صورت به ازای هر   ،   . مجموعه هم‌دسته‌های  راست(چپ)  که در آن  با عمل   یک گروه تشکیل می‌دهد  که در آن را گروه خارج قسمتی  به وسیله  می‌نامند و با علامت  نشان می‌دهند.


\end{defi}
\begin{defi}
فرض کنیم  ، در این صورت   را یک زیرگروه نرمال مینیمال  گروه می‌نامیم هرگاه تنها زیرگروه‌های نرمال  مشمول در   ، و خود  باشند.
 
\end{defi}

\begin{theorem}[ قضیه اساسی گروه‌های آبلی متناهی ]
فرض کنیم  گروه آبلی  و متناهی بوده باشد، در این صورت    .
\end{theorem}

\begin{proof}
به   مراجعه کنید.
\end{proof}
هر گروه آبلی  متناهی به دو صورت مختلف با حاصل‌ضرب مستقیم گروه‌های دوری یکریخت است.
\begin{itemize}
\item[1) با حاصل‌ضرب مستقیمی به صورت  

که در آن هر عدد  ، عدد را عاد می‌کند. ]
\item[2) با حاصل‌ضرب مستقیمی به صورت  

که در آن ها اعداد اول ( نه لزوما متمایز) هستند. در هر دو حالت حاصل‌ضرب مستقیم منحصربفرد است.]
\end{itemize}

\begin{defi}
فرض کنیم  یک گروه متناهی باشد و فرض کنیم  یک عدد اول باشد، در این صورت یک زیرگروه  از که مرتبه آن بزرگترین توانی از  باشد  که مرتبه را عار می‌کند  را یک  - زیرگروه سیلوی می‌نامیم.
 
\end{defi}


\begin{theorem}
فرض کنیم  یک گروه از مرتبه  باشد که در آن    یک عدد اول است و   .  در این صورت ذارای  زیرگروه ازمرتبه  است.
\end{theorem}
\begin{theorem}
فرض کنیم یک زیرگروه متناهی باشد و فرض کنیم  یک زیرگروه  باشد در این صورت یک زیر گروه سیلوی مانند   وجود دادرد به طوری که    .
\end{theorem}
\begin{theorem}
فرض کنیم یک گروه متناهی باشد  در این صورت به ازای هر عدد اول ،  یک رده تزویجی منحصربفرد از زیرگروه‌ها را تشکیل می‌دهند. به عبارت دیگر، اگر  یک زیرگروه سیلوی باشد، آن‌گاه      .
\end{theorem}
\begin{theorem}
فرض کنیم یک گروه متناهی باشد و یک عدد اول باشد که در این صورت  دارای عضوی از مرتبه   است.
\end{theorem}
\begin{proof}
فرض کنیم  ، طبق قضیه   سیلو، چون  ، لذا   .  لذا   وجود دارد. طبق قضیه لاگرانژ، مرتبه  به صورت   است که درآن . در این صورت مرتبه    . پس   عضوی از مرتبه    در   است.
\end{proof}
\begin{exam}
مربع  را در نظر بگیریم و فرض کنیم   مجموعه رئوس مربع باشد. فرض کنیم  مجموعه جایگشت‌هایی از  باشد که می‌توانند به وسیله  یک حرکت فیزیکی مربع در فضای سه بعدی ایجاد شوند. برای مثال، تصور کنیم  که مربع به اندازه درجه در جهت عکس عقربه‌های ساعت  حول مرکزش دوران داده شود. در این صورت  راس به مکانی که قبلا در آن قرار داشت منتقل می‌شود و   ،   عضو متناظر  نگاشت    است. به طور مشابه، یک انعکاس حول محور عمودی ، نگاشت 

را ایجاد می‌کند. اگر ابتدا دوران و سپس انعکاس را انجام دهیم، نتیجه دقیقا مانند یک انعکاس حول محور قطر  خواهد بود و عضو متناظر  با این عمل، نگاشت ترکیب 

می‌توان نشان  داد که یک گروه است که دارای هشت عضو می‌باشد. یک روش برای شمردن اعضا، تمرکز روی یک ضلع خاص مانند   است. بعد از یک دوران با مکان اولیه یکی از چهار ضلع یکی خواهد شد  و در آن مکان، می‌تواند در دئ جهت مختلف باشد. این کل هشت حالت ممکن برای  مکان  را ایجاد می‌کند.

هشت عضو   ، جایگشت‌هایی هستند که  به وسیله  چهار انعکاس (حول محورهای   ،   ،   ،   و  ) و چهار دوران    ،   ،   ، و  ایجاد می‌شوند گروه   را  گروه دو وجهی  از مرتبه    می‌نامند  و با    نشان می‌دهند.

کلمه دو وجهی بر دو طرف جلو و پشت مربع اشاره دارد که به وسیله نصفی از اعضای گروه  تغییر داده می‌شود.
اگر به جای یک مربع، ما با یک  ضلعی منتظم شروع بکنیم، گروه  دو وجهی حاصل را با   نشان می‌دهیم و  دارای  عضو خواهد بود. همانند   ، نصف اعضای   متناظر با انعکاس   و نصف دیگر   (به همراه نگاشت همانی ) متناظر با دوران‌هایی درون صفحه‌ایی هستند.


\end{exam}
\begin{defi}
گروه کواترنسیون تعمیم یافته را با    و    ، نشان می‌دهیم.
این گروه از مرتبه   بوده   و با مولدها و رابطه‌های زیر تعریف می‌شود.

گروه   به عنوان گروه کواترنسیون شناخته شده و از مرتبه   می‌باشد. 
\end{defi}
\begin{defi}
گروه آبلی   را مقدماتی می‌گوییم  هرگاه یک عدد اول مانند وجود داشته باشد به قسمی که  به ازای هر  ،  .
\end{defi}
\begin{theorem}

\end{theorem}



\section{نظریه گراف}
\begin{defi}
یک گراف عبارت است از سه تایی مرتب   ، که در آن  مجموعه‌ای ناتهی، مجموعه‌ای مجزا از   و   یک نگاشت وقوع است که به هر عضو    یک زوج نامرتب (یکسان یا متمایز) از نظیر می‌کند. عضوهای   را رأس‌های   و  عضوهای   را یال‌های  می‌نامند. اگر برای یال   از داشته باشیم: آن‌گاه    .
\end{defi}
\begin{defi}
تعداد رأس‌های گراف را مرتبه گراف گوییم.
\end{defi}
\begin{defi}
درجه رأس    از گراف    برابر تعداد یال‌های واقع بر  است  و با نماد   نمایش داده می‌شود.
\end{defi}
\begin{defi}
یالی که ابتدا و انتهای  آن یکسان باشد طوقه نامیده می‌شود.
\end{defi}
\begin{defi}
گراف را ساده گوییم  هرگاه بین هر دو رأس گراف، حداکثر یال رسم شده باشد و هم‌چنین طوقه و جهت نیز وجود نداشته باشد.
\end{defi}
\begin{defi}
رأس مجاور به رأس   در گراف  رأسی است که با یالی  به وصل شده باشد. 
\end{defi}
\begin{defi}
فرض کنیم یک گراف با مجموعه رئوس   و مجموعه  یال‌های  باشد. اگر گرافی باشد که   و     ، آن‌گاه   را زیرگراف  می‌نامیم.
\end{defi}
\begin{defi}
گراف را ساده گوییم  هرگاه بین هر دو رأس گراف، حداکثر یال رسم شده باشد و هم‌چنین طوقه و جهت نیز وجود نداشته باشد.
\end{defi}
\begin{defi}
رأس مجاور به رأس   در گراف  رأسی است که با یالی  به وصل شده باشد. 
\end{defi}
\begin{defi}
فرض کنیم یک گراف با مجموعه رئوس   و مجموعه  یال‌های  باشد. اگر گرافی باشد که   و     ، آن‌گاه   را زیرگراف  می‌نامیم.
\end{defi}
\begin{defi}
گراف را ساده گوییم  هرگاه بین هر دو رأس گراف، حداکثر یال رسم شده باشد و هم‌چنین طوقه و جهت نیز وجود نداشته باشد.
\end{defi}
\begin{defi}
رأس مجاور به رأس   در گراف  رأسی است که با یالی  به وصل شده باشد. 
\end{defi}
\begin{defi}
فرض کنیم یک گراف با مجموعه رئوس   و مجموعه  یال‌های  باشد. اگر گرافی باشد که   و     ، آن‌گاه   را زیرگراف  می‌نامیم.
\end{defi}
\begin{defi}
زیر گراف  از  را یک زیر گراف حقیقی(سره) گوییم هرگاه   (). 
\end{defi}
\begin{defi}
زیرگراف   از   را   زیرگراف  القایی نامیم هرگاه هر یال  که پایان‌هایش (دوسریال) در  باشد. در  نیز قرار بگیرد.
\end{defi}
\begin{defi}
گرافی که ار آن هر دو  رأس دلخواه،   با یک یال به هم وصل شده باشند. یا به عبارت دیگر، گرافی که تمام رأس‌های آن دو به دو بها هم مجاور باشند را گراف کامل گوییم.
\end{defi}
\begin{defi}
فرض کنیم    یک  گراف باشد. بزرگ‌ترین زیر گراف کامل را یک خوشه می‌نامیم. تعداد رئوس خوشه را عدد خوشه‌ای نامیده  و با  نماد       نمایش می‌دهیم.
\end{defi}
\begin{defi}
گذری که رأس تکراری نداشته باشد مسیر نامیده می‌شود.
\end{defi}
\begin{defi}
مسیر بسته را دور می‌نامیم.
\end{defi}
\begin{defi}
گراف را هم‌بند گوییم اگر بین هر دو رأس دلخواه آن، مسیری وجو داشته باشد، در غیر این صورت گراف را ناهم‌بند گوییم.
\end{defi}
\begin{defi}
زیرگراف   از را فراگیر گوییم  هرگاه   .
\end{defi}
\begin{defi}
دو گراف که تعداد یکسانی رأس دارند  و  این رأس‌ها نیز به طور مشابه به یک‌دیگر متصل گشته‌اند. یک‌ریخت نامیده می‌شوند. 
\end{defi}
شرط لازم   و کافی   برای یک‌ریخت بودن دو گراف  این است که  بعد از مشاهده تعداد یال‌ها، درجه هر رأس و نظیر کردن  دو گراف به یک‌دیگر، می‌گوییم این دو گراف شرایط هم‌ریختی را دارند(شرط لازم). اکنون باید هر رأس گراف به دیگری نظیر شود. اگر همه رأس‌ها در  دو  گراف دو به دو نظیرند گوییم این دو گراف یک‌ریختند(شرط کافی).
\begin{defi}
گرافی که  در آن درجه تمام  رئوس با هم برابر باشند منتظم نامیده می‌شود.
\end{defi}
\begin{defi}
گراف   از مرتبه را  منتظم گوییم هرگاه   درجه هر  رأس برابر با   باشد. یعنی      .
\end{defi}

\begin{defi}
گراف کامل از مرتبه   تمام رئوسش از درجه   است یعنی   ها منتظم‌اند.
\end{defi}
\begin{defi}
هر گراف کامل منتظم است. اما عکس تین وطلب درست نیست. در نتیجه می‌توان گرافی منتظم یافت که کامل نباشد. مثلا  گراف زیر  منتظم است انا کامل نیست.
\end{defi}
\begin{defi}
دور گرافی است که تعداد برابر یال و رأس دارد به طوری که رئوس می‌توانند  بر روی یک دایره قرار بگیرند و هر  دو رأس این گراف مجاورند اگر و تنها اگر روی دایره به سورت متوالی قرار گرفته باشند. به عبارت دقیق‌تر در یک گراف با مجموعه رئوس   و مجموعه یال‌های   ،  یک دور عبارت است از دنباله‌ای به شکل     () که    و به جزء این دو رأس در دنباله، همه یال‌ها و رأسها غیر تکراری باشند.
\end{defi}
\begin{defi}
گراف   را گراف دوبخشی گوییم هرگاه مجموعه رئوس یک گراف مانند    به دو بخش      و    افراز شود به گونه‌ای که به همه رئوس  وصل شده باشند و آن را با نماد    نشان می‌دهیم.   
\end{defi}

\begin{lemma}
گراف  دوبخشی است اگر و تنها اگر شامل هیچ دور فردی نباشد.
\end{lemma}
\begin{proof}
فرض کنیم  ، یک گراف دوبخشی باشد. پس    که    . پس   فرض کنیم    یک دور    در   باشد(). فرض کنیم  ()   ،   چون  دوبخشی است   و           یک یال در   در   است. پس   به همین ترتیب، چون  یک یال در  است پس   . هم‌چنین  یک یال   در  است که ایجاب می‌کند  . مشخص است که  (یک عدد فرد ) و  ( یک عدد زوج) اما یال   و این‌که   ایجاب می‌کند  . لذا   یک عدد زوج است.  لذا گراف فاقد دور فرد می‌باشد.

برعکس فرض کنیم   دور فرد نداشته باشد. نشان می‌دهیم  دوبخشی است. فرض کنیم  یک رأس  دلخواه در  باشد. بدیهی است که  برخی  از رئوس  با فاصله‌شان زوج  و برخی دیگر  فرد است. قرار می‌دهیم:


نشان می‌دهیم   و   .   بدیهی است   .   اگر      ، آن‌گاه    عدد زوج     و عدد فرد   که یک تناقض است.  فرض کنیم    و   دو رأس دلخواه از   باشند  و  یک یال در باشد. چون    ، پش   یک عدد زوج است. از طرفی   ایجاب می‌کند  که نیز یک عدد زوج باشد
طول دور =    عدد فرد     که این یک تناقض است. چون گراف فاقد دور به طول فرد است.  



مشابه این نشان می‌دهیم بین دو رأس دلخواه  هیچ یالی وجود ندارد.  فرض کنیم (فرض خلف)    و  دو رأس دلخواه   از   باشند و   یک یال  در  باشد. چون   پس   یک عدد فرد است. از طرفی    ایجاب می‌کند که نیز   یک عدد فرد باشد.


که این یک تناقض است. چون گراف   فاقد دور به طول  فرد است. پس   دوبخشی است.
\end{proof}

\begin{defi}
یک گراف ساده، درخت است اگر و تنها اگر  بین هر دو رأس متمایز  آن فقط و فقط یک مسیر یکتا وجود داشته باشد. 
\end{defi}

\begin{defi}
گراف بدون دور و هم‌بند یک درخت نامیده می‌شود.
\end{defi}
\begin{defi}
درخت ستاره‌ای، درختی است که در آن یکی از رأس‌ها به تمام رأس‌های دیگر وصل شده است. در ستاره‌ها رأس مرکزی را هسته(مرکز) می‌نامیم. هسته ستاره‌ها همیشه از درجه   می‌باشد.
\end{defi}
\begin{defi}
گراف مسطح گرافی است که می‌تواند در یک صفحه محاط شود. برای مثال، یک گراف  مسطح را می‌توان به گونه‌ای رسم کرد که یال‌هایش یکدیگر را تنها در رأس‌ها قطع کنند.
\end{defi}
\begin{defi}
انقباض  از  یک گراف  را انقباضی از  می‌نامیم اگر با انقباض متوالی یال‌هایی از به وجود آمده باشند. واضح است اگر انقباضی  از   باشد، آن‌گاه   و   .
\end{defi}
\begin{exam}
نشان می‌دهیم   و   مسطح نیستند.   برای   داریم:    و     و بنابراین    پس  مسطح نیست. 

برای   ، هر ناحیه حداقل لبه می‌یاشدو لذا   .  اگر مسطح باشد،    . بنابراین     و این یک تناقض است   و بنابراین  مسطح نیست.


\end{exam}


\begin{theorem*}[قضیه کوراتوسکی]
گراف  مسطح اگر و تنها اگر  شامل گرافی که ایزومرفیسم با هر دو گراف‌های    و   نباشد.
\end{theorem}
\begin{proof}
با توجه به مثال بالا، واضح است که یک گراف شامل زیرگرافی ایزومرفیسم با  یا غیرمسطح است.  برعکس نشان می‌دهیم هر گراف  غیرمسطح شامل  زیرگرافی ایزومرفیسم    با یا   است(بوتری  و مورتی  را ملاحظه کنید).
\end{proof}

با استفاده از قضیه کوراتوسکی، قضیه زیر را به صورت دیگری بیان می‌کنیم.

\begin{theorem}
یک گراف مسطح است  اگر و تنها اگر  شامل زیرگرافی قابل انقباض با   و   نباشد. 
\end{theorem}
\begin{proof}
ابتدا فرض کنیم  گراف  غیرمسطح است، در این صورت بنا به قضیه کوراتوسکی، شامل یک زیرگراف  است که  با  یا  ایزومورفیسم است. از انقباض متوالی یالهایی از  که حداقل از یک رأس درجه  می‌گذرند، ملاحظه می‌شود   که با   یا   قابل انقباض   است. حال فرض کنیم    ،   دارای  زیر گراف   است که قابل انقباض   به است   و  فرض کنیم    ،   از   حاصل انقباض زیرگراف  از  است.  شکل  را ملاحظه کنید. رأس   از ،  بر سه   ،   و  قرار دارد، این سه یال  به عنوان یال‌های  بر سه رأس (که لزوما یکسان نیستند)   ، و می‌گذرند.

در صورتی که  ،  و متمایز باشند،  یک رأس   از   و سه مسیر  از  به این رئوس وجود دارد، این مسیرها فقط در یک‌دیگر را قطع می‌کنند. اگر رئوس متمایز نباشند ساختار مشابهی به کار می‌رود. در این صورت مسیرها به رئوس تبدیل می‌شود. در نتیجه    و سه یال  منشعب از آن جایگزین می‌شود. اگر این دستورالعمل را برای هر رأس از  ، انجام دهیم و مسیرهای حاصل به یالهای   اضافه شوند، زیرگراف حاصل به وضوح   با   ایزومرفیسم است، یعنی  (بنا به قضیه کوراتوسکی)  غیر مسطح است (شکل   را ملاحظه کنید)
\end{proof}
\begin{defi}
یک گراف  را اویلری گوییم، هرگاه تمام رئوس   ،   شامل دنباله   بسته   بوده باشد (همبند) باشد. دو شرط لازم یرای اویلری بودن گراف عبارتند از  
1) همبند بودن گراف
2) زوج بودن درجه همه رأس‌های گراف 

\end{defi}

\begin{theorem}
اگر گرافی مانند  یک دور اویلری داشته باشد، آن‌گاه درجه هر رأس این گراف زوج می‌باشد.
\end{theorem}
\textbf{سوال:}
آیا عکس قضیه بالا برقرار است؟ خیر، با این‌که درجه همه راش‌ها زوج می‌باشد. اما به خاطر ناهمبندی، دور اویلری وجود ندارد. عکس قضیه اویلر زمانی برقرار است که شرط هم‌بندی قید شود.

\begin{defi}

در حالت کلی،  اگر مرتبه گراف  ،  باشد فاصله دو رأس دلخواه از هم، می‌تواند باشد. 

در گراف کامل   ،  فاصله هر دو رأس متمایز از هم برابر با یک است.
\end{defi}

\begin{defi}
فرض کنیم   یک گراف باشد. در این صورت بزرگ‌ترین اندازه یک خوشه  در  را عدد خوشه‌ای می‌نامیم.

\end{defi}

\begin{defi}

یک رأس از یک  گراف را رأس غالب می‌نامیم، هرگاه  با هر رأس دیگر از از   مجاور باشد.

واضح است که  عضو همانی از گروه   ،  یک رأس غالب از هر گراف توانی بهبود یافته است.
\end{defi}

\begin{defi}
گراف توانی بهبود یافته    را غالب می‌نامیم هرگاه دارای رأس غالب دیگری  به غیر از  باشد.

\end{defi}