אנחנו נעסוק בגרפים לא מכוונים בלי לולאות כלומר המקיימים <math>\forall v\in V : \{v,v\}\not\in E</math>ובלי צלעות כפולות, כלומר לא מופיע פעמיים <math>\{v,w\}</math> ב <math>E</math>. בנוסף הגרפים שלנו יהיו סופיים.
'''הגדרה''' מחלקות השקילות של יחס זה נקראים רכיבי קשירות.
=תרגילים=
תרגיל: יהי גרף לא מכוון <math>G=(V,E)</math> בעל <math>3\leq n</math> קודקודים.
אם בגרף <math>n\leq m </math> צלעות אזי בגרף יש מעגל.
הוכחה: באינדוקציה.
עבור <math>n=3</math> אזי יש מדובר במשולש (לא יכול להיות יותר מ -4 צלעות ב-3 קודקודים) ואכן מתקיים כי יש מעגל.
נניח כי הטכנה נכונה עבור <math>n</math> ונוכיח עבור <math>n+1</math>.
יהי יהי גרף לא מכוון <math>G=(V,E)</math> בעל <math>3< n+1</math> קודקודים ו- <math>n+1\leq m </math> צלעות.
אפשרות 1: קיים <math>v\in V</math> מדרגה 1. נוריד את הקודקוד הזה (ואת כל הצלעות שחלות בו) ונקבל גרף חדש עם <math>n</math> קודקודים ו<math>n\leq m-1 </math> צלעות. לפי הנחת האינדוקציה קיים בו מעגל. מעגל זה קיים גם בגרף בו התחלנו.
אפשרות 2: לכל קודקוד יש דרגה גדולה שווה 2. נבחר <math>v_0\in V</math> ונצא ממנו לאחד משכניו. מפה נמשיך למסלול רנדומאלי כך שאם הולכים מ <math>v\to u</math> הצעד הבא לא יהיה <math>u\to v</math> (זה אפשרי כי כל קודקוד יש לפחות 2 שכנים אז אם נכנסים אליו משכן א ניתן לצאת משכן ב). כיוון שיש מספר סופי של קודקודים נקבל חזרה על קודקוד בשלב כלשהוא. בפעם הראשונה שנקבל חזרה קיבלנו מעגל!
תרגיל: