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 (અન્ય ત્રણ પ્રતિબંધિત રૂપરેખાંકનો સાથે) પ્રતિબંધિત મેટ્રોઇડ માઇનર્સ દ્વારા ગ્રાફિક મેટ્રોઇડ્સના લાક્ષણિકતામાં દેખાય છે. સંદર્ભો પ્લાનર આલેખ આલેખ લઘુ સિદ્ધાંત આલેખ સિદ્ધાંતમાં પ્રમેય