Page 50 - C112215

.تسا جوز یددع ،فارگ ره درف یاه سأر دادعت :هجیتن
رد .دشاب G فارگ ِ جوز سوئر همه هعومجم B و G فارگ ِ درف ِ سوئر همه هعومجم A و فارگ کی G مینک ضرف :تابثا
ٔ
ٔ
ٔ
ٔ
. ∑ deg( ) = ∑ deg( ) + ∑ deg( ) میراد تروص نیا
v
v
v
∈
∈
∈
v V () vA vB
G
v
دهد یم هجیتن نیا و تسا جوز یددع زین ∑ deg( ) نیاربانب )؟ارچ( .دنا جوز ∑ deg( ) و ∑ deg( ) یفرط زا
v
v
∈
G
v ∈A v ∈B vV ()
)؟ارچ( .تسا جوز یددع n (A) هک
تیلاعف
هفرطود هطبار کی هورگ نیا یاضعا نیب یتسود دینک ضرف .دیریگب رظن رد ار سلاک کی نازومآ شناد زا هرفن 7 عمج کی
ٔ
:نونکا .تسین تسود یرگید اب کی چیه ای و دنا تسود مه اب ود ره ای اهنآ زا رفن ود ره ینعی ،تسا
ِ
ار سأر ود ره سپس ،دیهد رارق سأر کی زومآ شناد ره یازا هب هک تروص نیا هب دیهد لیکشت ار G یسأر 7 فارگ )فلا
.دنشاب تسود مه اب سأر ود نآ اب رظانتم نازومآ شناد رگا اهنت و رگا دینک لصو مه هب
ِ
.دشاب 3 اب ربارب لصاح فارگ ِ سوئر مامت هجرد درادن ناکما هک دیهد ناشن لبق هیضق زا هدافتسا اب )ب
ٔ
ٔ
مامت درادن ناکما دشاب درف یددع عمج کی دارفا دادعت رگا هک دیهد ناشن فارگ زا هدافتسا اب و لبق لحارم هب هجوت اب )پ
.دنشاب عمج نآ رد تسود یدرف دادعت یاراد ،عمج نآ تارفن

تیلاعف
ای رت گرزب لوط هب ریسم کی لماش G هک میهد ناشن میهاوخ یم .δ (G) ≥ 4 میشاب هتشاد و دشاب فارگ کی G دینک ضرف

.تسا 4 یواسم

.دشاب v سأر نآ مینک ضرف )؟ارچ( .تسا لصتم یرگید سأر هب v ًامتح .میریگ یم رظن رد G رد ار v هاوخلد سأر 1
2 1 1
.دشاب v سأر نآ مینک یم ضرف )؟ارچ( .تسا لصتم v سأر زج هب یسأر هب v ًامتح 2
3 1 2
.دشاب v سأر نآ مینک یم ضرف )؟ارچ( تسا لصو V(G ) - {v , v } هعومجم زا یسأر هب v ًامتح 3
2 ٔ
4 1 3
.دشاب v سأر نآ مینک یم ضرف )؟ارچ( تسا لصو V (G ) - {v , v , v } هعومجم زا یسأر هب v ًامتح 4
3 ٔ
5 1 2 4
.تسا G فارگ رد 4 لوط هب ریسم کی v v v v v ریسم 5
1 2 3 4 5

سلاک رد راک

.دیروآ تسد هب ار G فارگ یاه لای دادعت ریز یاه تلاح زا کی ره رد
.تسا مظتنم ـ K یسأر n فارگ کی G )فلا

(G = K n ) .تسا لماک یسأر n فارگ کی G )ب

40 یزاس لدم و فارگ :مود لصف