1- أثبت أن بيان بيترسون لا يملك بيانا جزئيا فوق الممتلئ.
2- أعط تلوينا ضلعيا صريحا لإثبات أن Xʼ(Qk) = ∆(Qk).
3- حدد العدد اللوني الضلعي للبيان Cn □ K2.
4- احصل على متباينة ل Xʼ(G) بدلالة e(G) و aʼ(G).
5- أثبت أن بيان بيترسون هو المتممة ل L(K5).
6- حدد عدد المثلثات في البيان الخطي لبيان بيترسون.
7- ليكن G بيانا بسيطا يخلو من الرؤوس المعزولة. أثبت أنه إذا كان L(G) مترابطا و منتظما، فإما أن يكون G منتظما، أ, أن يكون بيانا ثنائي الفرع بحيث تكون درجات الرؤوس في كل مجموعة مجزأة متساوية. (Ray-Chaudhuri [1967])
8- ليكن G بيانا بسيطا مترابطا ضلعيا من الدرجة k. أثبت أن L(G) مترابط من الدرجة k، و مترابط ضلعيا من الدرجة 2k-2. (مساعدة : للقطع الضلعي الأصغر [S,Ṡ] في L(G)، صف ماذا يقابل القطع في G، و احسب عدد أضلاعه بدلالة الرؤوس في G).
9- أعط تلوينا ضلعيا صريحا لتثبت أن Xʼ(Kr,s) = ∆ (Kr,s).
10- أثبت أنه يوجد لكل بيان ثنائي الفرع G بيان H ثنائي الفرع بسيط منتظم من الدرجة ∆(G) يحوي G.
11- إثبات خوارزمي للنظرية 7.1.7 ليكن G بيانا ثنائي الفرع مع درجة كبرى تساوي k. و ليكن ƒ تلوينا ضلعيا فعليا من الدرجة k لبيان جزئي H من G. و ليكن uv ضلعا ليس في H. باستخدام مسار يتناوب مسار في لونين، أثبت أن ƒ يمكن أن يبدل، ثم يوسع إلى تلوين ضلعي فعلي من الدرجة k ل H+uv. استنتج أن∆(G) Xʼ(G) =.
12- استخدم نظرية بروكس في بيان ملائم لتثبت أنه إذا كان G بيانا بسيطا له ∆(G) =3، فإنه قابل للتلوين الضلعي من الدرجة 4. (تعليق : النتيجة هي حالة خاصة من نظرية فايزنج ؛ لا تستخدم نظرية فايونج لإثبات هذا).
13- ليكن G و H بيانين بسيطين غير تافهين. استخدم نظرية فايزنج لتثبت أن ∆(H) Xʼ(H) =. يؤدي إلى أن∆(G □ H) Xʼ(G □ H) =.
14- مخمنة فوق الممتلئ ← مخمنة التحليل إلى العوامل من الدرجة 1 (الملاحظة 12.1.7) : a) أثبت أنه في البيان المنتظم الذي درجته زوجية، يكون البيان الجزئي المحدث فوق ممتلئ إذا و فقط إذا كان البيان الجزئي المحدث من بقية الرؤوس فوق ممتلئ. b) ليكن G بيانا بسيطا منتظما من الدرجة k درجته 2m، ويملك بيانا جزئيا فوق ممتلئ. أثبت أن k
15- إذا أعطيت تلوينا ضلعيا للبيان G، اجعل c(v) يرمز إلى عدد الألونا المختلفة التي تظهر على الأضلاع الواقعة v. من بين التلوينات الضلعية جميعها التي درجتها k للبيان G، يكون تلوين ما هو الأمثل () إذا كان يعظم :∑vϵv(G)c(v) a) أثبت أنه إذا كان لم تكن أي مركبة ل G حلقة فردية، فإن g يملك تلوينا ضلعيا من الدرجة 2 حيث يظهر كلا اللونين عند كل رأس درجته 2 على الأقل. (مساعدة : استخدم الحلقات الأويلرية). b) ليكن ƒ تلوينا ضلعيا أمثل من الدرجة k، بحيث يظهر اللون a على الأقل مرتين عند الرأس uϵV(G)، أما اللون b فلا يظهر عند u. و ليكن H التي تحتوي u هي حلقة فردية. c) ليكن G بيانا ثنائي الفرع. استنتج من الفرع (b) أن G قابل للتلوين الضلعي من الدرجة ∆(G) (تعليق : تقود هذه الأفكار لإثبات نظرية فايزنج.) (Fournier [1973])
16- ل n≠8، أثبت أن L(Kn) هو البيان البسيط المنتظم من الدرجة (2n-4) الوحيد الذي رتبته (n2) بحيث تملك الرؤوس غير المتجاورة أربعة جيران مشتركة، في حين تمتلك الرؤوس المتجاورة n-2 جارا مشتركا. (تعليق : عندما n = 8، فإن ثلاثة بيانات استثنائية تحقق الشروط). .(Hoffman [1960]. Chang[1959])
17- أثبت أن كل مسار في ذي الاثني عشر وجها يقع في حلقة هاملتونية.
18- لأي القيم r يكون Kr,r هاملتونيا ؟
19- ل n˃1، أثبت أن Kn,n يملك (n-1)!n!/2 حلقة هاملتونية.
20- ليكن G بيانا ثنائي الفرع هاملتونيا، و اختر x,y ϵV(G). أثبت أن G-x-y يملك مواءمة تامة إذا و فقط إذا كان من x و y على جهتين مختلفتين من التجزئة الثنائية ل G. طبق هذا لتثبيت أن حذف مربعي وحدة من لوحة الشطرنج (8 x 8) يبقى على لوحة يمكن أن تجزأ إلى مستطيلات 1 في 2 إذا و فقط إذا تحقق أن المربعين المحذوفين يملكان لونين مختلفين.
21- يأكل فأر مكعب 3 x 3 x3 من الجبن بأكل المكعبات الجزئية 1 x 1 x 1 جميعها. إذا بدأ عند زاوية مكعب جزئي، و في كل مرة يتحرك إلى مكعب جزئي (تشارك بوجه مساحته 1)، هل يستطيع الفأر عمل هذا و الانتهاء بأكل المكعب الجزئي الذي في المركز ؟ هات طريقة لعمل ذلك، أو أثبت استحالة ذلك (تجاهل الجاذبية).
22- أنشئ عائلة مكونة من عدد لا نهائي من البيانات غير الهاملتونية التي تحقق الشرط الضروري لقضية 3.2.7.
23- هاملتوني مقابل أويلري : a) جد بيانا غير أويلري مترابطا من الدرجة 2 بحيث يكون بيانه الخطي هاملتونيا. b) أثبت أن L(G) يكون هاملتونيا. إذا و فقط إذا كان G يملك مسربا مغلقا يحتوي على نقطة طرفية واحدة على الأقل من كل ضلع. (Harary, Nash-Williams [1965])
24- ليكن G البيان المنتظم من الدرجة 3 الذي نحصل عليه من بيان بيترسون باستبدال مثلث بأحد الرؤوس، و من ثم مواءمة رؤوس المثلث مع جيران الرأس المحذوف. أثبت أن G ليس هاملتونيا. (تعليق : ما عدا هذا البيان و بيان بيترسون، فإن كل بيان منتظم من الدرجة k، و مترابط من الدرجة 2 و له 3k+3 رأسا على الأكثر يكون هاملتونيا). (Hilbig [1986])
25- يكون البيان G قابلا للتلوين الضلعي من الدرجة k بصورة فريدة (uniquely) إذا كانت التلوينات الضلعية الفعلية من الدرجة k للبيان G جميعها تحدث التجزئة للأضلاع نفسها. أثبت أن كل بيان منتظم من الدرجة 3 قابل للتلوين الضلعي من الدرجة 3 بصورة فريدة يكون هاملتونيا. (Greenwell-Kronk [1973])
26- ضع n نقطة حول دائرة. ليكن Gn هو البيان المنتظم من الدرجة 4 الذي نحصل عليه بضم كل نقطة إلى أقرب نقطتين إليها في كل اتجاه. إذا كان n≥5، فأثبت أن Gn هو اتحاد لحلقتين هاملتونيتين.
27- أثبت أن الجداء الديكارتي لبيانين هاملتونينا. استنج أن المكعب Qk ذا البعد k هامتلوني لكل k≥2.
28- ليكن G(k,t) صف البيانات التي لها k فرعا و المترابطة بحيث تكون كل مجموعة مجزأة حجمها t، و كل بيان جزئي محدث من مجموعتين مجزأتين هو مواءمة حجمها t. ل k≥4 و t≥4ـ أنشئ بيانا في G(k,t) بحيث يكون غير هاملتوني. (مساعدة : يوجد بيان في G(4,4) مع مجموعة فيها 3 عناصر، و حذفها يخلف أربع مركبات ؛ عمم هذا المثال. تعليق :G(3,t) = [C3t]، و أيضا كل بيان في G(k,3) يكون هاملتونيا) (Ayel [1982])
29- أثبت أن المتانة لبيان بيترسون هي 3/4.
30- ليكن t(G) يرمز إلى المتانة ل G : a) أثبت أن. t(G) ≤k(G)/2 (Chvẚtal[1973]). b) أثبت أن المساواة تتحقق في فرع (a( للبيانات التي تخلو من المخالب. (مساعدة : خذ في الحسبان مجموعة S حيث ǀSǀ=t(G). c(G-S) ( Mattews-Sumner[1984]).
31- ليكن G بيانا بسيطا و ليس غابة، و يملك خصرا يساوي 5 على الأقل. أثبت أن Ġ يكون هاملتونيا. (مساعدة : استخدام شرط أور (Ores condition) (N. Graham)
32- احصل على تمهيدية 9.2.7 (الكفاية لشرط أور) من النظرية 13.2.7 (الكفاية لشرط كفتال). (Bondy [1978])
33- أثبت أو انقض : إذا كان G بيانا بسيطا له ثلاثة رؤوس على الأقل، و كان يملك a(G) رأسا على الأقل درجاتها n(G)-1، فإنه يكون هاملتونيا.
34- ليكن G بيانا بسيطا ثنائي بالتجزئة الثنائية X,Y حيثn/2 >1 ǀXǀ = ǀYǀ =. و لتكن dn،....،d1 هي درجات الرؤوس فيه، حيث d1≤…≤ dn. ليكن Gʼ هو أصغر بيان حاو للبيان (supergraph)G بحيث Gʼ[Y] = Kn/2 : a) أثبت أن G يكون هاملتونيا إذا و فقط إذا كان Gʼ هاملتونيا. وصف العلاقة بين متتاليتي الدرجات لكل من G و Gʼ. b) افترض أن dk>k أو dn/2>n/2-k عندما k≤n/4. أثبت أن G يكون هاملتونيا. (مساعدة : افترض أن متتالية الدرجة ل Gʼ لا تحقق شرط كفتال لبعض قيم i
35- شرط ضروري لمترابط هاملتوني : (Moon [1965a]). a) أثبت أن كل بيان مترابط هاملتوني على أربعة رؤوس على الأقل يملك [3n(G)/2 ضلعا على الأقل. b) أثبت أن الحد في فرع (a) هو أفضل ما يمكن بإثبات أن Cm □ K2 يكون مترابطا هاملتونيا إذا كان m فرديا.
36- أثبت أنه إذا كان G بيانا بسيطا بحيث متتالية درجاته هي dn≥...≥d1 و كان d1+d2، فإن G يملك مسار طوله على d1+d2+1، إلا إذا كان G هو الرابط n-( d1+1) رأست معزولا مع بيان d1+1 من الرؤوس، أو كان G=pkd1V K1 لبعض قيم P ≥3 ([1967b]Ore ).
37- لقد خمن سكوت سميت أن إذا أخذنا أي أطول حلقتين في بيان مترابط من الدرجة k دائما فإنهما تملكان k رأسا مشتركا على الأقل. إن طريق الحل أدناه يصلح لقيم k الصغيرة : a) افترض أن G بيان منتظم من الدرجة 4 على n من الرؤوس بحيث إن G هي إتحاد لحلقتين ( قد تظهر أضلاع متكررة). ليكن Gʼ بيانا منتظما من الدرجة 4 على n+2 من الرؤوس، و بحيث نحصل عليه من G بتقسيم جزئي لضلعين، و إضافة ضلع مزدوج بين الرأسين الجديدين. بين أن Gʼ هو أيضا اتحاد لحلقتين مولدتين إذا كان n≤5. b) استخدم فرع (a) لتستنتج أن أي زوج من الحلقات الأطول في بيان مترابط من الدرجة k يتقاطع في k نقطة على الأقل إذا كان k≤6 (Burr, Smith).
38- ليكن G بينا أويلري. و لتكن Vʼ هي مجموعة الحلقات الأويلرية في G، مع الأخذ في الحسبان أن حلقة و معكوسها هما الشيء نفسه. افترض أن Gʼ هو البيان على مجموعة الرؤوس Vʼ بحيث تكون حلقتان متجاورتين إذا و فقط إذا كانت إحداهما تظهر من الأخرى بعكس الترتيب الضلعي على حلقة جزئية مغلقة فعلية. أثبت أن Gʼ يكون هاملتونيا إذا كان ∆(G) ≤ 4. (مساعدة : استخدم الاستقراء على الرؤوس التي درجتها 4، و هذا يثبت وجود حلقة هاملتونية لكل ضلع في Gʼ. (تعليق : يتحقق الاستنتاج أيضا دون تقييد على ∆(G) (Zhang- Guo [1986] Xia [1982])
39- أثبت أن كل دوري يملك مسار هاملتونيا (مسار موجه مولد). (مساعدة : استخدم التطرفية). (Re'dei [1934])
40- أحصل على النظرية 8.2.7 (الكفاية لشرط ديراك في البيانات) من النظرية 22.2.7 (الكفاية لشرط غويلا و هوري على البيانات الموجهة). (مساعدة : حول بيانا بسيطا G إلى بيان موجه صارم باستبدال كل ضلع بزوج من الأضلاع الموجهة في اتجاهين متعاكسين).
41- أثبت أن كل بيان هاملتوني منتظم من الدرجة 3 يملك تلوبن تايت.
42- اعرض بيانات بسيطة منتظمة من الدرجة 3 تكون : a) سويةـو لكنها غير قابلة للتلوين الضلعي من الدرجة 3. b) مترابطة من الدرجة 2، و لكنها غير قابلة للتلوين الضلعي من الدرجة 3. c) سوية مع ترابط 2، و لكنها ليست هاملتونية.
43- أثبت أن كل بيان مستوي أعظمي غير K4 يكون قابلا للتلوين الوجهي من الدرجة 3.
44- دون استخدام نظرية الأولان الأربعة، أثبت أن كل بيان مستو هاملتوني يكون قابلا للتلوين الوجهي من الدرجة 4 (دون أي افتراض حول درجات الروؤس).
45- ليكن G تثليثا مستويا : a) أثبت أن الثنوي G* يملك معاملا من الدرجة 2. b) استخدم فرع (a) لتثبيت أن الرؤوس في G من الممكن أن تلوين بلونين بحيث يملك كل وجه رؤوس كلا اللونين. (مساعدة : استخدم الفكرة في الإثبات لنظرية (2.3.7) Penaud [1975], Burstein [1974]
46- أثبت أن تلوينا فعليا من الدرجة 4 للبيان ذي العشرين وجها يستعمل كل لون 3 مرات بالضبط.
47- لقد أثبت ويتني [1931]أن كل تثليث سوي مترابط من الردجة 4 يكون هاملتونيا. استخدم هذا لتحخفف مسألة الألوات الأربعة إلى المسألة التي تثبت أن كل بيان سوي هاملتوني قابل للتولين من الدرجة 4.
48- جد بيانا سويا مترابطا من الدرجة 5. هل يوجد بيان سوي مترابط من الدرجة 6 ؟
49- ليكن G تثليثا مستويا. أثبت أنه يملك تجزئة رأسية إلى مجموعتين محدثا غابات إذا و فقط إذا كان G* هاملتونيا. (Stein [1970])
50- ليكن G بيانا منتظما من الدرجة 3. أثبت أنه إذا كان G اتحادا لحقلتين، فإنه يكون قابلا للتلوين الضلعي من الدرجة 3.
51- "سناركات الزهرة" ليكن Gk و Hkأنشئا في (المثال 13.3.7) : a) أثبت أن Gk قابل للتلوين الضلعي من الدرجة 3. b) أثبت أن Hk غير قابل للتلوين الضلعي من الدرجة 3 عندما يكون k فرديا. (Isaacs [1975])
52- أثبت أن كل قطع ضلعي ل Kk □ Ct و الذي لا يعزل رأسا يملك 2k ضلعا على الأقل.
53- أثبت أن تطبيق عملية الجداء النقطي (التعريف 12.3.7) على سناركين يعطي سناركا ثالثا. ([1975] Isaacs).
