گراف ۱ مسطح

منبع}}
در نظریه توپولوژیک گراف، یک گراف ۱ - مسطح گرافی است که می توان آن را طوری در صفحهٔ اقلیدسی ترسیم کرد که هر یال حداکثر یک تقاطع با یال های دیگر داشته باشد. به عبارت دیگر، هیچ یالی با دو یال دیگر متقاطع نباشد. به چنین ترسیمی هم یک ترسیم ۱ - مسطح از گراف می گویند ( گرافی که حداقل یک ترسیم ۱ - مسطح داشته باشد، گراف ۱ - مسطح نامیده می شود ) .
گرهارد رینگل ( ۱۹۹۵ ) اولین کسی بود که به مطالعهٔ گراف های ۱ - مسطح پرداخت. او نشان داد که این گراف ها را می توان با حداکثر ۷ رنگ رنگ آمیزی کرد. بعداً مشخص شد که تعداد دقیق رنگ های مورد نیاز برای رنگ آمیزی این گراف ها در بدترین حالت، عدد ۶ است. گراف کامل K۶ نمونه ای است که نشان می دهد تعداد ۶ رنگ در بعضی حالات مورد نیاز است. با این حال، اثبات اینکه ۶ رنگ همیشه کافی خواهد بود، پیچیده تر از اینهاست.
انگیزهٔ رینگل این بود که بتواند نوعی از رنگ آمیزی کامل را برای گراف های مسطح حل کند، که در آن تمام رئوس و وجوه یک گراف مسطح را همزمان طوری رنگ می کنیم که هیج دو رأس مجاوری همرنگ نبوده، هیج دو وجه مجاوری همرنگ نبوده، و هیچ رأس و وجهی که مجاور هستند همرنگ نباشند. این کار به وضوح توسط ۸ رنگ قابل انجام است، کافی است قضیه چهاررنگ را بر روی گراف داده شده و گراف همزاد ( dual ) آن با دو مجموعهٔ مجزا از ۴ رنگ به طور مجزا اعمال کنیم. با این حال، برای دستیابی به تعداد کمتری از رنگ ها می توان یک گراف کمکی تشکیل داد که یک رأس به ازای هر رأس یا وجه گراف مسطح داده شده دارد، و دو رأس این گراف کمکی مجاور هستند اگر و فقط اگر دو رأس/وجه متناظر آن ها در گراف اصلی مجاور باشند. یک رنگ آمیزی رأسی این گراف کمکی معادل یک رنگ آمیزی رأسی - وجهی گراف مسطح اصلی است. این گراف کمکی یک گراف ۱ - مسطح است، و از اینجا بود که مسئله رنگ آمیزی رأسی - وجهی رینگل منجر به رنگ آمیزی رأسی گراف ۱ - مسطح شد، و اکنون می دانیم که هر دوی این مسائل با ۶ رنگ قابل حل هستند. گرچه گراف کامل K۶ را نمی توان به عنوان یک گراف کمکی تشکیل داد، اما برای نمونه اگر گراف مسطح منشور مثلثی را بخواهیم رنگ آمیزی وجهی - رأسی کنیم، یازده رأس و وجه آن به ۶ رنگ نیاز دارند، چون به هیچ سه تایی از آن ها نمی توان یک رنگ اختصاص داد.
هر گراف ۱ - مسطح با n رأس حداکثر ۴n − ۸ یال دارد. قوی تر اینکه، هر ترسیم ۱ - مسطح حداکثر n − ۲ تقاطع دارد؛ حذف یک یال از هر زوج یال های متقاطع، یک گراف مسطح را باقی می گذارد، که می تواند حداکثر ۳n − ۶ یال داشته باشد، که بلافاصله نتیجه می دهد گراف ۱ - مسطح اصلی حداکثر می توانست ۴n − ۸ یال داشته باشد. با این حال، بر خلاف گراف های مسطح ( که تمام گراف های مسطح بیشینه روی یک مجموعه از رئوس مشخص، تعداد یکسانی از یال ها دارند ) ، گراف های ۱ - مسطح بیشینه ای ( که هیچ یال جدیدی با حفظ ۱ - مسطح بودن نمی توان به آن ها اضافه کرد ) وجود دارند که تعداد یال بسیار کمتری از ۴n − ۸ دارند. محدودیت ۴n − ۸ برای حداکثر تعداد یال ها در یک گراف ۱ - مسطح می تواند نشان دهد که گراف کامل K۷ یک گراف ۱ - مسطح نیست، چون دارای ۷ رأس و ۲۱ یال بوده و ۴n − ۸ = ۲۰ < ۲۱.