Wagner's theorem
گراف تھیوری میں، ویگنر تھیوریم پلانر گراف کی ریاضیاتی ممنوع گراف کی خصوصیت ہے، جس کا نام کلاؤس ویگنر کے نام پر رکھا گیا ہے، جس میں کہا گیا ہے کہ ایک محدود گراف پلانر ہے اگر اور صرف اس صورت میں جب اس کے نابالغوں میں نہ تو K5 (پانچ عمودی پر مکمل گراف) اور نہ ہی K3,3 (یوٹیلیٹی گراف، چھ عمودی پر ایک مکمل دو طرفہ گراف) شامل ہو۔ یہ گراف مائنرز کے نظریہ کے ابتدائی نتائج میں سے ایک تھا اور اسے رابرٹسن سیمور تھیوریم کے پیش رو کے طور پر دیکھا جا سکتا ہے۔ تعریفیں اور بیان کسی دیئے گئے گراف کی طیارہ سرایت یوکلڈین سطح میں گراف کی ایک ڈرائنگ ہے، جس میں اس کے عمودی حصوں کے لیے پوائنٹس اور اس کے کناروں کے لیے منحنی خطوط ہوتے ہیں، اس طرح کہ کناروں کے جوڑوں کے درمیان واحد چوراہے دونوں کناروں کے مشترکہ اختتامی نقطہ پر ہوتے ہیں۔ دیئے گئے گراف کا ایک چھوٹا سا دوسرا گراف ہے جو عمودی حصوں کو حذف کرنے، کناروں کو حذف کرنے اور کناروں کو سکڑنے سے بنتا ہے۔ جب کسی کنارے کو تنگ کیا جاتا ہے، تو اس کے دو اختتامی نکات کو ضم کر کے ایک واحد ورٹیکس بنایا جاتا ہے۔ گراف مائنر تھیوری کے کچھ ورژنوں میں سنکچن کے نتیجے میں گراف کو سیلف لوپس اور متعدد ملحقہ علاقوں کو ہٹا کر آسان بنایا جاتا ہے، جبکہ دیگر ورژنوں میں ملٹی گراف کی اجازت ہے، لیکن اس تغیر سے ویگنر کے تھیوریم پر کوئی فرق نہیں پڑتا ہے۔ ویگنر کے نظریہ میں کہا گیا ہے کہ ہر گراف میں یا تو پلانر ایمبیڈنگ ہوتی ہے، یا دو اقسام میں سے ایک معمولی، مکمل گراف K5 یا مکمل دو طرفہ گراف K3,3 ہوتا ہے۔ (یہ بھی ممکن ہے کہ ایک ہی گراف میں دونوں قسم کے معمولی ہو۔) اگر دیا ہوا گراف طیارہ دار ہے، تو اس کے تمام نابالغ بھی ہیں: ورٹیکس اور ایج ڈیلیشن واضح طور پر طیارہ داری کو برقرار رکھتے ہیں، اور کنکریکٹڈ ایج کے دو اختتامی نکات میں سے ایک کو جگہ پر چھوڑ کر اور کنکریکٹڈ ایج کے راستے میں دوسرے اختتامی نقطہ پر واقع ہونے والے تمام کناروں کو روٹ کرکے، کنکریٹ کو محفوظ رکھنے کے طریقے سے بھی کنکریٹ کیا جا سکتا ہے۔ ایک معمولی-کم سے کم غیر پلینر گراف ایک ایسا گراف ہے جو پلینر نہیں ہے، لیکن جس میں تمام مناسب نابالغ (کم از کم ایک حذف یا سنکچن سے بنے نابالغ) پلینر ہیں۔ ویگنر کے نظریہ کو بیان کرنے کا ایک اور طریقہ یہ ہے کہ صرف دو معمولی-کم سے کم غیر پلینر گراف، K5 اور K3,3 ہیں۔ ایک اور نتیجہ جسے بعض اوقات ویگنر تھیوریم بھی کہا جاتا ہے کہ چار جڑا ہوا گراف پلانر ہے اگر اور صرف اس صورت میں جب اس میں کوئی K5 معمولی نہ ہو۔ یعنی، اعلی سطح کی کنیکٹوٹی کو فرض کرتے ہوئے، گراف K3,3 کو خصوصیت میں غیر ضروری بنایا جا سکتا ہے، جس سے صرف ایک ممنوعہ نابالغ، K5 رہ جاتا ہے۔ اسی کے مطابق، کیلمینس-سیمور قیاس آرائی میں کہا گیا ہے کہ 5 سے منسلک گراف صرف اس صورت میں ہموار ہے جب اس میں ٹوپولوجیکل معمولی کے طور پر K5 نہ ہو۔ تاریخ اور کوراتووسکی کے نظریہ سے تعلق ویگنر نے 1937 میں دونوں نظریات شائع کیے، 1930 میں کوراتووسکی کے نظریہ کی اشاعت کے بعد، جس کے مطابق ایک گراف پلانر ہے اگر اور صرف اس صورت میں جب اس میں ذیلی گراف کے طور پر ان ہی دو ممنوعہ گرافوں میں سے کسی ایک کی ذیلی تقسیم نہ ہو۔ K5 اور K3,3۔ ایک لحاظ سے، کوراتووسکی کا نظریہ ویگنر کے نظریہ سے زیادہ مضبوط ہے: ذیلی تقسیم کے عمل سے بننے والے ہر راستے میں ایک کنارے کے علاوہ سب کو سکڑ کر ایک ذیلی تقسیم کو ایک ہی قسم کے معمولی میں تبدیل کیا جا سکتا ہے، لیکن ایک معمولی کو ایک ہی قسم کے ذیلی تقسیم میں تبدیل کرنا ہمیشہ ممکن نہیں ہوتا ہے۔ تاہم، دو گرافوں K5 اور K3,3 کے معاملے میں، یہ ثابت کرنا سیدھا ہے کہ ایک گراف جس میں ان دو گرافوں میں سے کم از کم ایک چھوٹا ہے، ان میں سے کم از کم ایک ذیلی تقسیم بھی ہے، لہذا دونوں تھیوریم مساوی ہیں۔ اثرات چار جڑے ہوئے گرافوں کے لیے ویگنر کے نظریہ کے مضبوط ورژن کا ایک نتیجہ ان گرافوں کی خصوصیت ہے جن میں K5 معمولی نہیں ہے۔ تھیوریم کو یہ کہتے ہوئے دوبارہ بیان کیا جا سکتا ہے کہ اس طرح کا ہر گراف یا تو پلینر ہے یا اسے آسان ٹکڑوں میں تقسیم کیا جا سکتا ہے۔ اس خیال کو استعمال کرتے ہوئے، K5-نابالغ سے پاک گرافوں کو ان گرافوں کے طور پر نمایاں کیا جا سکتا ہے جو پلانر گرافوں اور آٹھ ورٹیکس ویگنر گراف کے امتزاج کے طور پر بنائے جا سکتے ہیں، جو کلک-سم آپریشنز کے ذریعے ایک ساتھ چپکے ہوتے ہیں۔ مثال کے طور پر، K3,3 کو اس طرح سے تین پلانر گرافوں کے کلکس کے مجموعے کے طور پر بنایا جا سکتا ہے، جن میں سے ہر ایک ٹیٹراہیڈرل گراف K4 کی نقل ہے۔ ویگنر تھیوریم گراف مائنرز کے نظریہ کا ایک اہم پیش خیمہ ہے، جس کا اختتام دو گہرے اور دور رس نتائج کے ثبوتوں پر ہوا: گراف اسٹرکچر تھیوریم (ویگنر کے K5-مائنر فری گرافز کے کلک-سم سڑنے کی عمومی شکل) اور رابرٹسن-سیمور تھیوریم (پلانر گرافز کی ممنوعہ معمولی خصوصیت کی عمومی شکل، جس میں کہا گیا ہے کہ نابالغوں کو لینے کے عمل کے تحت بند ہونے والے ہر گراف فیملی میں ممنوعہ نابالغوں کی ایک محدود تعداد کی خصوصیت ہوتی ہے)۔ ویگنر کے نظریہ کے اینالاگس کو میٹروئڈز کے نظریہ تک بھی بڑھایا جا سکتا ہے: خاص طور پر، وہی دو گراف K5 اور K3,3 (تین دیگر ممنوعہ ترتیبات کے ساتھ) ممنوعہ میٹروئڈ نابالغوں کے ذریعہ گرافک میٹروئڈز کی خصوصیت میں ظاہر ہوتے ہیں۔ حوالہ جات پلانر گراف گراف مائنر تھیوری تھیوریمز ان گراف تھیوری