1- أثبت العبارة الآتية أو انقضها : يوجد رأس قطع للبيان السوي إذا و فقط إذا كان الممر المحيط بأي وجه حلقة.
2- أثبت أو انقض : a) كل بيان جزئي لبيان سوي يكون سويا. b) كل بيان جزئي لبيان غير سوي يكون غير سوي.
3- أثبت أن البيانات المشكلة بحذف ضلع واحد من K5 و K3,3 تكون بيانات سوية.
4- جد قيم r و s التي تجعل Kr,s سويا.
5- أثبت العبارة الآتية أو انقضها : يوجد رأس قطع للبيان السوي إذا و فقط إذا كان الممر المحيط بأي وجه حلقة.
6- يعرف البيان السوي الخارجي الأعظمي على أنه بيان سوي خارجي بسيط بحيث لا يكون بيانا جزئيا مولدا لبيان سوي خارجي بسيط أكبر. افترض أن G بيان سوي خارجي أعظمي له ثلاثة رؤوس على الأقل. أثبت أن G مترابط من الدرجة 2.
7- أثبت أنه يوجد رأس درجته تساوي 5 على الأكثر في كل بيان سوي بسيط.
8- استخدم النظرية 23.1.6 لتبرهن أن كل بيان بسيط سوي عدد رؤوسه أقل من 12 يحوي رأسا درجته تساوي 4 على الأكثر
9- أثبت العبارة الآتية أو انقضها : لا توجد بيان سوي ثنائي الفرع بسيط درجته الصغرى تساوي 4 على الأقل.
10- افترض أن G بيان سوي أعظمي. أثبت أن G* مترابط ضلعيا من الدرجة 2 و منتظم من الدرجة 3.
11- ابن (جد) بيانا سويا منتظما من الدرجة 3 قطره 3 و له 12 رأسا. (تعليق : أثبت T.Barcume أن مثل هذا البيان ليس له أكثر من 12 رأسا).
12- أثبت العبارة الآتية أو انقضها : إذا كان g بيانا مستويا مترابطا من الدرجة 2 درجته الصغرى 3، فإن البيان الثنوي G* يكون بيانا بسيطا.
13- أثبت بالاستقراء على عدد الأوجه أن البيان المستوي G يكون ثنائي الفرع إذا و فقط إذا كان طول كل وجه عدد زوجيا.
14- أثبت أن مجموعة من الأضلاع في بيان مستو مترابط G تشكل شجرة مولدة ل G إذا و فقط كانت الأضلاع الثنوية للأضلاع المتبقية في G تشكل شجرة مولدة ل G*.
15- البيان الثنوي الضعيف (WeaK dual) للبيان G هو البيان الذي نحصل عليه من G* بحذف الرأس الموجود في الوجه G. أثبت أن البيان الثنوي الضعيف لبيان مستو خارجي عبارة عن غابة.
16- إثبات بديل لصيغة أويلر : a) استخدم المنحنيات المضلعة (ليست صيغة أويلر) للإثبات بالاستقراء على n(G) أن كل طمر سوي لشجرة G يحوي وجهها واحد. b) أثبت صيغة أويلر بالاستقراء على عدد الحلقات.
17- أثبت أن كل بيان مستو على n من الرؤوس يشاكل بيانه الثنوي يجب أن يحوي 2n-2 ضلعا. و لكل n≥4 جد بيانا مستويا بسيطا على n من الرؤوس يشاكل بيانه الثنوي.
18- لكل n≥2، جد أكبر عدد من الأضلاع في بيان خارجي بسيط له n من الرؤوس بإعطاء ثلاثة براهين كالآتي : a) بالاستقراء على n. b) باستخدام صيغة أويلر. c) بإضافة رأس في الوجه غير المحدود، و استخدام النظرية 23.1.6.
19- أفترض أن G بيان مستو منتظم من الدرجة 3، و مترابط بحيث يقع كل رأس من رؤوسه في وجه واحد طوله يساوي 4، و كذلك في وجه واحد طوله 6، و في وجه طوله 8 أيضا : a) حدد عدد الأوجه من كل طول بدلالة n(G). b) استخدم صيغة أويلر و فرع (a) لتحديد عدد أوجه G.
20- أثبت أن متممة البيان السوي البسيط الذي له 11 رأسا على الأقل هي بيان غير سوي. ابن بيانا سويا بسيطا على ثمانية رؤوس بحيث يكون هذا البيان ذاتي التتام (Self Complementary) أي أن متممته هي البيان نفسه.
21- افترض أن G بيان سوي أعظمي. أثبت أنه إذا كانت S مجموعة ثلاثية فاصلة للبيان G*، فإن G*-S يحوي مركبتين (chappell).
22- ابن عائلة غير منتهية من البيانات السوية البسيطة التي درجتها الصغرى تساوي 5 بحيث يكون لكل منها 12 رأسا درجة كل منها تساوي 5 (مساعدة : عدل الثنعشري).
23- أثبت أنه إذا كان G بيانا سويا بسيطا له أربعة رؤوس على الأقل، فيوجد فيه أربعة رؤوس على الأقل درجة كل منها أقل من 6 لكل قيمة من قيم n الزوجية حيث n ≥ 8، جد بيانا سويا بسيطا على n من الرؤوس له أربعة رؤوس بالضبط، درجة كل منها أقل من 6، (Grtinbaum – MotzKin [1963]).
24- افترض أن S مجموعة n من النقاط في المستوى بحيث تساوي المسافة بين x و y في المستوى 1 على الأقل لكل x,y ϵ S. أثبت أنه يوجد على الأكثر 3n – 6 زوجا v.u في S بحيث تساوي المسافة في المستوى بين u و بالضبط 1v.
25- إذا أعطيت أعدادا صحيحة k ≥ 2 و l ≥ 1 بحيث إن Kl عدد زوجي، فابن بيانا سويا له K وجها بالضبط، و طول كل وجه من هذه الوجوه يساوي l.
26- حدد أقل عدد من الأضلاع بمكن حذفه من بيان بيترسون للحصول على بيان جزئي سوي.
27- نظرية فاري. افترض أن R منطقة محاطة بمتعدد أضلاع بسيط له على الأكثر خمس حواف (يعني مضلع بسيط أن الأضلاع عبارة عن قطع مستقيمة لا تتقاطع). أثبت أنه يوجد في R نقطة ترى R كلها، بمعنى أن القطعة المستقيمة من x إلى أي نقطة في R لا تقطع حدود R استخدم هذا لتبرهن استقرائيا أنه يوجد لكل بيان سوي طمر على شكل خطوط مستقيمة.
28- استخدم نظرية كوارتوسكي لتبرهن أن البيان G يكون سويا خارجيا إذا و فقط إذا خلا G من بيان جزئي يشكل تقسيما ل K4 أو ل K23 (مساعدة : لتطبيق نظرية كورارتوسكي ؛ جد تعديلا مناسبا ل G أن هذا أسهل كثيرا من تقليد إثبات نظرية كواراتوسكي).
29- إذا كان هناك بيان مترابط من الدرجة 3، و له ستة رؤوس على الأقل، و يحوي تقسيما ل K5، فبرهن أن G يحوي تقسيما ل K3,3، (Wagner [1937]).
30- أفترض أن H بيان، درجته الكبرى تساوي 3 على الأكثر. أثبت أن بيانا G يحوي تقسيما ل H إذا و فقط إذا كان G يحوي بيانا جزئيا قابلا للتقليص إلى H
31- لقد أثبت و اجنر العام 1937 م أن الشرط الثاني ضروري و كاف ليكون البيان Gسويا، و هو : لا يمكن الحصول على K5 أو K3,3 من خلال إجراء عمليات الحذف و التقليص للأضلاع : a) أثبت أن حذف الأضلاع و تقليصها يحافظ على السوية، و استنتج من ذلك أن شرط و اجنر ضروري. b) استخدم نظرية كواراتوسكس لإثبات أن شرط واجنر كاف.
32- أثبت أن البيان G يكون سويا إذا و فقط إذا كان بيان تعارض كل حلقة C في G ثنائي الفرع (Tutte [1958]).
33- افترض أن x و y رأسان لبيان سوي G أثبت أن يوجد ل G طمر سوي فيه x و y على الوجه نفسه إلا إذا وجدت حلقة C في G – x – y، بحيث إن x و y ينتميان إلى شظايا C- متعارضة في G (مساعدة : استخدام نظرية كواراتوسكي. تعليق : لقد أثبت توت هذا النتيجة دون استخدام نظرية كواراتوسكي كما استخدمها لإثبات هذه النظرية).
34- افترض أن G بيان مستو بسيط مترابط من الدرجة 3 يحوي حلقة C أثبت أن C لكون حدودا لوجه في G إذا و فقط إذا وجدت في G شظية –C واحدة بالضبط. (تعليق : لقد أثبت توت عام 1963 م هذه النتيجة للحصول على نتيجة ويتني (Whitneys [1933b]) و هي أنه يوجد-مبدئيل- طمر سوي واحد فقط للبيانات السوية المترابطة من الدرجة 3. انظر أيضا (Kelmans [1981a]).
35- افترض أن G بيان سوي خارجي له n من الرؤوس، و افترض أيضا أن P مجموعة فيها n نقطة في المستوى، بحيث إنه لا توجد ثلاثة منها على الخط نفسه إن النقاط القصوى ل P تحدث مضلعا محدبا يحوي باقي النقاط في داخله : a) افترض أن P1 و p2 نقاط قصوى متتابعة في P، أثبت على وجود نقطة p ϵ P-[p1, p2] بحيث إن : 1) لا توجد أي نقطة من P داخل P1P2P) و 2) يوحد خط 1 يمر في P و يفصل P1 عن P2، و يقطع P فقط عند P، و يوجد بالضبط 2-1 نقطة من نقاط P محتواة في جانب L الذي يحوي P2، b) أثبت أنه يوجد ل G طمر على شكل خطوط مستقيمة بحيث ترسل رؤوسها إلى P كلها. (مساعدة : استخدم فرع (a) لإثبات النتيجة الأثوى و هي أنه : إذا كان كل من v1 و v2
36- استخدم نظرية الألوان الأربعة لتبرهن أن كل بيان سوي خارجي يكون قابلا للتلوين بثلاثة ألوان.
37- هات نصا لخوارزمية كثيرة حدود زمنية بحيث تأخذ بيانا سويا كمدخل، و تنتج تلوينا فعليا لخمسة ألوان لهذا البيان.
38- يكون البيان G مضمحلا (متفسخا) من الدرجة k (k-degenerate) إذا وجد في كل بيان جزئي منه رأس درجته تساوي k على الأكثر، أثبت أن البيان المضمخل (المتفسخ) من الدرجة k يكون قابلا للتلوين ب k + 1 لونا.
39- جد عدد التقاطع لكل من K2,2,2,2 و K4,4، و عدد التقاطع لبيان بيترسون كذلك.
40- استخدم نظرية الأولان الأربعة لتبرهن أن كل بيان سوي بتفكك إلى بيانين ثنائيي الفرع. (Hedetniemi [1969]. Mabry [1995])
41- دون استخدام نظرية الألوان الأربعة، أثبت أن كل بيان سوي له 12 رأسا على ألأكثر يكون قابلا للتلوين بأربعة ألوان. استخدم هذا لتبرهن أن كل بيان سوي له 32 رأسا على الأكثر يكون قابلا للتلوين بأربعة ألوان.
42- افترض أن H تشكل في تثليث سوي (التعريف 2.3.6). و افترض كذلك أن ’H هو البيان الذي نحصل عليه من وضع درجات الرؤوس كعلامات دالة على جيران رؤوس الحلقة، و من ثم نحذف رؤوس الحلقة. أثبت إمكانية استرداد H من ’H.
43- جد تشكلا حجم حلقته يساوي 5 في تنثليث سوي، بحيث إن درجة كل رأس تساوي 5 على الأقل، و بحيث يوجد أكثر من رأس داخلي واحد.
44- أثبت أن كل تشكل سوي حجم حلقته يساوي 4 على الأكثر يكون مصغرا. (مساعدة : الحلقة عبارة عن حلقة فاصلة C. أثبت أنه إذا كانت التثليثات الأصغر قابلة للتلوين بأربعة ألوان، فإن للفلق C- من G أربعة ألوان تتوافق على C)، (BirKhoff [1913]).
45- نعرف صالة عرض (معرض) الآثار (الفنون) الذي له جدران على أنه مضلع إضافة إلى بعض الأوتار غير المتقاطعة التي تسمى "جدرانا" و التي تصل (تربط) بين الرؤوس كل جدار داخلي يحتوي على فتحة صغيرة تسمى "مدخلا" إذا وضع الحارس على المدخل، فإنه لا يستطيع رؤية كل شيء داخل الغرفتين المتجاورتين، و لكن الحارس الذي لا يكون موجودا في المدخل، فإنه لا يستطيع أن يرى أبعد من الجدار. حدد أصغر عدد t من الحراس يلزم استخدامه لحراسة معرض فني له جدران بحيث تكون كل نقطة داخلية مرئية من قبل أحد الحراس . (Hutchinson [1995] .RStinalgen[1999])
46- أثبت أن البيان السوي الأعظمي يكون قابلا للتلوين بثلاثة ألوان إذا و فقط إذا كان هذا البيان أويلريا. (مساعدة : لإثبات الكفاية ؛ استخدم الاستقراء على n(G) اختر زوجا مناسبا أو ثلاثة رؤوس متجاورة لاستبدالها بأضلاع) (Heawood [1898]).
47- أثبت أنه يمكن تجزئة رؤوس بيان سوي خارجي بسيط إلى مجموعتين، بحيث يكون البيان الجزئي الذي تحدثه كل مجموعة عبارة عن اتحاد منفصل لمسارات (مساعدة : عرف تجزئة باستخدام نوعية المسافة (زوجية أم فردية) بالنسبة إلى رأس مثبت). (Mih6K-[1983] .AKiyama-Era-Geryacia-Watanabel 1989].Goddard [1991])
48- أثبت أن المكعب الرباعي Q4 بيان غير سوي. فكك Q4 إلى بيانين متشاكلين سويين لذا، فإن سمك Q4 يساوي 2.
49- فكك K9 إلى ثلاثة بيانات سوية متشاكلة زوجا زوجا.
50- أثبت أنه لا يوجد بيان جزئي سوي منK3,2,2 بحيث يكون لهذا البيان الجزئي 15 ضلعا، و استخدم هذا لتعطي إثباتا ثانيا لحقيقة أن v(K3,2,2)≥2.
51- ليكن Mn البيان الذي نحصل عليه من الحلقة Cn بإضافة أوتار تربط بين الرؤوس المتقابلة (إذا كان n عددا زوجيا)، و تربط بين الرؤوس شبه المتقابلة (إذا كان n عدد فرديا). إن البيان M منتظم من الدرجة 3 إذا كان n زوجيا، و منتظم من الدرجة 4 إذا كان n عددا فرديا. جد v(Mn)، (Guy-Harary [1967] ).
52- لكل عدد صحيح موجب k، ابن (جد) بيانا يمكن طمره على الطارة إلا أن رسمه في المستوى يحوي K تقاطعا على الأقل (مساعدة : يكفي إعطاء عائلة طارية (يمكن طمرها على الطارة) واحدة بحيث تكون سهلة الوصف : استخدم القضية 13.3.6).
53- جد (ابن) طمرا على الطارة لبيان بسيط غير ثنائي الفرع منتظم من الدرجة 3 بحيث يكون طول كل وجه فيه عدد زوجيا.
54- نقول : إن طمر لبيان على سطح معين يكون منتظما إذا كان لوجوهه جميعها الطول نفسه جد طمرا منتطما على الطارة لكل من : K4,4، و K3,6، و K3,3.
55- أثبت صيغة أويلر للجنس :y إن عدد رؤوس أي طمر و أضلاعه و أوجهه لخلية ثنائية لبيان على سطح Sy يحقق العلاقة n-r+f=2-2y. استنتج من ذلك أنه يوجد (n-2+2y)3 ضلعا على الأكثر لبيان بسيط له n من الرؤوس، و قابل للطمر على Sy.
56- لكل عدد صحيح موجب k، استخدم صيغة أويلر لتبرهن أنه يوجد بيان سوي G، بحيث إن k≤Y(G □ K2)
