Wagner's theorem
গ্রাফ তত্ত্বে, ওয়াগনারের উপপাদ্য হল সমতলীয় গ্রাফের একটি গাণিতিক নিষিদ্ধ গ্রাফ বৈশিষ্ট্যায়ন, যা ক্লাউস ওয়াগনারের নামে নামকরণ করা হয়েছে, যেখানে বলা হয়েছে যে একটি সীমাবদ্ধ গ্রাফ সমতলীয় হয় যদি এবং শুধুমাত্র যদি তার অপ্রধানগুলিতে কে5 (পাঁচটি শীর্ষে সম্পূর্ণ গ্রাফ) বা কে3,3 (ইউটিলিটি গ্রাফ, ছয়টি শীর্ষে একটি সম্পূর্ণ দ্বিদলীয় গ্রাফ) অন্তর্ভুক্ত না থাকে। এটি গ্রাফ মাইনর তত্ত্বের প্রাচীনতম ফলাফলগুলির মধ্যে একটি এবং রবার্টসন-সেমুর উপপাদ্যের অগ্রদূত হিসাবে দেখা যেতে পারে। সংজ্ঞা এবং বিবৃতি একটি প্রদত্ত গ্রাফের প্ল্যানার এম্বেডিং হল ইউক্লিডীয় সমতলে গ্রাফের একটি অঙ্কন, যার শীর্ষগুলির জন্য পয়েন্ট এবং প্রান্তগুলির জন্য বক্ররেখা রয়েছে, এমনভাবে যে দুটি প্রান্তের জোড়ার মধ্যে একমাত্র ছেদ দুটি প্রান্তের একটি সাধারণ শেষ বিন্দুতে থাকে। প্রদত্ত গ্রাফের একটি ছোট অংশ হল শীর্ষস্থান মুছে ফেলা, প্রান্ত মুছে ফেলা এবং প্রান্ত সংকুচিত করে গঠিত আরেকটি গ্রাফ। যখন একটি প্রান্ত সংকুচিত হয়, তখন এর দুটি প্রান্তবিন্দু একত্রিত হয়ে একটি একক শীর্ষ গঠন করে। গ্রাফ মাইনর তত্ত্বের কিছু সংস্করণে সংকোচনের ফলে গ্রাফটি স্ব-লুপ এবং একাধিক সংলগ্নতা সরিয়ে সরলীকৃত করা হয়, অন্য সংস্করণে মাল্টিগ্রাফ অনুমোদিত, তবে এই প্রকরণটি ওয়াগনারের উপপাদ্যের সাথে কোনও পার্থক্য করে না। ওয়াগনারের উপপাদ্য বলে যে প্রতিটি গ্রাফের হয় একটি প্ল্যানার এম্বেডিং থাকে, অথবা দুটি প্রকারের মধ্যে একটি ছোট, সম্পূর্ণ গ্রাফ K5 অথবা সম্পূর্ণ দ্বিদলীয় গ্রাফ K3,3। (একটি একক গ্রাফের জন্য উভয় ধরনের ছোট আকার থাকাও সম্ভব।) যদি একটি প্রদত্ত গ্রাফ সমতলীয় হয়, তবে তার সমস্ত অপ্রধানগুলিওঃ শীর্ষ এবং প্রান্ত মুছে ফেলা স্পষ্টতই সমতলীয়তা বজায় রাখে, এবং প্রান্ত সংকোচন একটি সমতলীয়-সংরক্ষণের উপায়েও করা যেতে পারে, সংকুচিত প্রান্তের দুটি শেষ বিন্দুর মধ্যে একটি জায়গায় রেখে এবং সংকুচিত প্রান্তের পথে অন্য শেষ বিন্দুতে আপতিত সমস্ত প্রান্তকে রাউটিং করে। একটি ক্ষুদ্র-ন্যূনতম অ-সমতলীয় গ্রাফ হল এমন একটি গ্রাফ যা সমতলীয় নয়, তবে এতে সমস্ত যথাযথ অপ্রাপ্তবয়স্ক (কমপক্ষে একটি অপসারণ বা সংকোচন দ্বারা গঠিত অপ্রাপ্তবয়স্ক) সমতলীয় হয়। ওয়াগনারের উপপাদ্যটি বর্ণনা করার আরেকটি উপায় হল যে কেবল দুটি ক্ষুদ্র-ন্যূনতম অ-সমতলীয় গ্রাফ রয়েছে, K5 এবং K3,3। আরেকটি ফলাফল যা কখনও কখনও ওয়াগনারের উপপাদ্য নামেও পরিচিত, বলে যে একটি চার-সংযুক্ত গ্রাফ সমতল হয় যদি এবং শুধুমাত্র যদি এটির কোনও K5 মাইনর না থাকে। অর্থাৎ, একটি উচ্চতর স্তরের সংযোগ ধরে নিয়ে, K3,3 গ্রাফটিকে চরিত্রায়নের ক্ষেত্রে অপ্রয়োজনীয় করে তোলা যেতে পারে, শুধুমাত্র একটি নিষিদ্ধ মাইনর, K5 রেখে। তদনুসারে, কেলম্যানস-সেমুর অনুমান বলে যে একটি 5-সংযুক্ত গ্রাফ সমতল হয় যদি এবং শুধুমাত্র যদি এটিতে টপোলজিকাল মাইনর হিসাবে K5 না থাকে। কুরাটোভস্কির উপপাদ্যের ইতিহাস এবং সম্পর্ক ওয়াগনার 1937 সালে উভয় উপপাদ্য প্রকাশ করেন, 1930 সালে কুরাটোভস্কির উপপাদ্য প্রকাশের পরে, যার মতে একটি গ্রাফ সমতল হয় যদি এবং শুধুমাত্র যদি এটি একটি উপগ্রাফ হিসাবে একই দুটি নিষিদ্ধ গ্রাফ K5 এবং K3,3 এর মধ্যে একটির একটি উপবিভাগ না থাকে। এক অর্থে, কুরাটোভস্কির উপপাদ্য ওয়াগনারের উপপাদ্যের চেয়ে শক্তিশালীঃ উপবিভাগ প্রক্রিয়া দ্বারা গঠিত প্রতিটি পথে একটি প্রান্ত ছাড়া বাকি সমস্ত প্রান্ত সংকুচিত করে একটি উপবিভাগকে একই ধরনের ক্ষুদ্র উপবিভাগে রূপান্তরিত করা যেতে পারে, তবে একটি ক্ষুদ্র উপবিভাগকে একই ধরনের উপবিভাগে রূপান্তর করা সবসময় সম্ভব হয় না। যাইহোক, K5 এবং K3,3 দুটি গ্রাফের ক্ষেত্রে, এটি প্রমাণ করা সোজা যে একটি গ্রাফ যাতে এই দুটি গ্রাফের মধ্যে কমপক্ষে একটি গৌণ হিসাবে থাকে তার মধ্যে অন্তত একটি উপবিভাগ হিসাবে থাকে, তাই দুটি উপপাদ্য সমতুল্য। প্রভাব চার-সংযুক্ত গ্রাফের জন্য ওয়াগনারের উপপাদ্যের শক্তিশালী সংস্করণের একটি পরিণতি হল যে গ্রাফগুলিতে কে5 মাইনর নেই সেগুলিকে চিহ্নিত করা। উপপাদ্যটিকে এই বলে পুনর্ব্যবহার করা যেতে পারে যে এই ধরনের প্রতিটি গ্রাফ হয় সমতলীয় অথবা এটিকে সহজ টুকরোতে বিভক্ত করা যেতে পারে। এই ধারণাটি ব্যবহার করে, কে5-ক্ষুদ্র-মুক্ত গ্রাফগুলিকে এমন গ্রাফ হিসাবে চিহ্নিত করা যেতে পারে যা প্ল্যানার গ্রাফ এবং আট-ভার্টেক্স ওয়াগনার গ্রাফের সংমিশ্রণ হিসাবে গঠিত হতে পারে, যা চক্র-সমষ্টি ক্রিয়াকলাপ দ্বারা একত্রিত হয়। উদাহরণস্বরূপ, কে3,3 এইভাবে তিনটি সমতলীয় গ্রাফের সমষ্টি হিসাবে গঠিত হতে পারে, যার প্রতিটি টেট্রাহেড্রাল গ্রাফ কে4-এর একটি অনুলিপি। ওয়াগনারের উপপাদ্যটি গ্রাফ মাইনর তত্ত্বের একটি গুরুত্বপূর্ণ অগ্রদূত, যা দুটি গভীর এবং সুদূরপ্রসারী ফলাফলের প্রমাণের মধ্যে শেষ হয়ঃ গ্রাফ স্ট্রাকচার উপপাদ্য (ওয়াগনারের কে5-মাইনর-মুক্ত গ্রাফের ক্লাইক-সাম ডিকম্পোজিশনের একটি সাধারণীকরণ) এবং রবার্টসন-সেমুর উপপাদ্য (প্ল্যানার গ্রাফের নিষিদ্ধ মাইনর চরিত্রায়নের একটি সাধারণীকরণ, যা উল্লেখ করে যে অপ্রাপ্তবয়স্কদের নেওয়ার ক্রিয়াকলাপের অধীনে বন্ধ হওয়া প্রতিটি গ্রাফ পরিবারের সীমাবদ্ধ সংখ্যক নিষিদ্ধ মাইনর দ্বারা একটি বৈশিষ্ট্যায়ন রয়েছে)। ওয়াগনারের উপপাদ্যের সাদৃশ্যগুলি ম্যাট্রয়েড তত্ত্ব পর্যন্ত প্রসারিত করা যেতে পারেঃ বিশেষত, একই দুটি গ্রাফ K5 এবং K3,3 (অন্যান্য তিনটি নিষিদ্ধ কনফিগারেশন সহ) নিষিদ্ধ ম্যাট্রয়েড অপ্রাপ্তবয়স্কদের দ্বারা গ্রাফিক ম্যাট্রয়েডের বৈশিষ্ট্যকরণে উপস্থিত হয়। তথ্যসূত্র প্ল্যানার গ্রাফ গ্রাফ ক্ষুদ্র তত্ত্ব গ্রাফ তত্ত্বের উপপাদ্য