ในทฤษฎีกราฟทฤษฎีบทโรเบิร์ตสัน-เซย์มัวร์ (เรียกอีกอย่างว่าทฤษฎีบทกราฟไมเนอร์^{[ 1 ]} ) ระบุว่ากราฟที่ไม่มีทิศทางซึ่งเรียงลำดับบางส่วนโดยความสัมพันธ์ ของ กราฟไมเนอร์ จะก่อให้เกิด การเรียงลำดับแบบกึ่งดี [ ^{2 ] หรือ}กล่าวอีกนัยหนึ่งคือ ทุกตระกูลของกราฟที่ปิดภายใต้การใช้ไมเนอร์สามารถกำหนดได้ด้วยเซตจำกัดของไมเนอร์ต้องห้ามในทำนองเดียวกับที่ทฤษฎีบทของแวกเนอร์ระบุลักษณะของกราฟระนาบว่าเป็นกราฟที่ไม่มีกราฟสมบูรณ์ หรือกราฟสองส่วนสมบูรณ์เป็นไมเนอร์ ${\displaystyle K_{5}}$${\displaystyle K_{3,3}}$

ทฤษฎีบทโรเบิร์ตสัน-เซย์มัวร์ได้รับการตั้งชื่อตามนักคณิตศาสตร์นีล โรเบิร์ตสันและพอล ดี. เซย์มัว ร์ ซึ่งพิสูจน์ทฤษฎีบทนี้ในชุดเอกสาร 20 ฉบับที่มีความยาวกว่า 500 หน้า ตั้งแต่ปี 1983 ถึง 2004 ^{[ 3 ]}ก่อนที่จะมีการพิสูจน์ ข้อความของทฤษฎีบทนี้เป็นที่รู้จักในชื่อสมมติฐานของวากเนอร์ตามชื่อของนักคณิตศาสตร์ชาวเยอรมันเคลาส์ วากเนอร์แม้ว่าวากเนอร์จะกล่าวว่าเขาไม่เคยตั้งสมมติฐานนี้เลยก็ตาม^{[ 4 ]}

ผลลัพธ์ที่อ่อนกว่าสำหรับต้นไม้นั้นบ่งชี้โดยทฤษฎีบทต้นไม้ของ Kruskal ซึ่ง Andrew Vázsonyiตั้งสมมติฐานไว้ในปี 1937 และ Joseph Kruskalและ S. Tarkowski พิสูจน์โดยอิสระในปี 1960 ^{[ 5 ]}

ไมเนอร์ของกราฟแบบไม่มีทิศทางคือกราฟใดๆ ที่สามารถได้มา จาก การหด ตัว ของขอบของกราฟและการลบขอบและจุดยอดของ กราฟ ตั้งแต่ศูนย์ครั้งขึ้นไปความสัมพันธ์ของไมเนอร์ก่อให้เกิดลำดับบางส่วนบนเซตของกราฟแบบไม่มีทิศทางจำกัดที่แตกต่างกันทั้งหมด เนื่องจากเป็นไปตามสัจพจน์สามข้อของลำดับบางส่วน ได้แก่ เป็นแบบสะท้อน (กราฟทุกกราฟเป็นไมเนอร์ของตัวเอง) เป็นแบบถ่ายทอด (ไมเนอร์ของไมเนอร์ของกราฟเป็นไมเนอร์ของกราฟ) และเป็นแบบปฏิสมมาตร (ถ้ากราฟสองกราฟและเป็นไมเนอร์ของกันและกัน กราฟทั้งสองจะต้องเป็นไอโซมอร์ฟิกกัน ) อย่างไรก็ตาม หากกราฟที่เป็นไอโซมอร์ฟิกกันยังคงถือได้ว่าเป็นวัตถุที่แตกต่างกัน ลำดับไมเนอร์บนกราฟจะก่อให้เกิดพรีออร์เดอร์ซึ่งเป็นความสัมพันธ์ที่เป็นแบบสะท้อนและถ่ายทอด แต่ไม่จำเป็นต้องเป็นแบบปฏิสมมาตร^{[ 6 ]}${\displaystyle G}$${\displaystyle G}$${\displaystyle G}$${\displaystyle G}$${\displaystyle G}$${\displaystyle G}$${\displaystyle G}$${\displaystyle G}$

กล่าวกันว่าลำดับก่อนหน้าจะก่อตัวเป็นลำดับกึ่งดี (well-quasi-ordering)หากไม่มีทั้งสายโซ่ที่ลดลงอย่างไม่มีที่สิ้นสุดหรือแอนติเชนที่ ไม่มีที่สิ้นสุด ^{[ 7 ]}ตัวอย่างเช่น ลำดับปกติบนจำนวนเต็มที่ไม่เป็นลบเป็นลำดับกึ่งดี แต่ลำดับเดียวกันบนเซตของจำนวนเต็มทั้งหมดไม่ใช่ เพราะมีสายโซ่ที่ลดลงอย่างไม่มีที่สิ้นสุด 0, −1, −2, −3... อีกตัวอย่างหนึ่งคือเซตของจำนวนเต็มบวกที่เรียงลำดับตามการหารลงตัวซึ่งไม่มีสายโซ่ที่ลดลงอย่างไม่มีที่สิ้นสุด แต่จำนวนเฉพาะประกอบเป็นแอนติเชนที่ไม่มีที่สิ้นสุด

ทฤษฎีบท Robertson–Seymour กล่าวว่ากราฟแบบไม่มีทิศทางจำกัดและกราฟไมเนอร์ก่อให้เกิดลำดับกึ่งดี ความสัมพันธ์ของกราฟไมเนอร์ไม่มีโซ่ที่ลดลงแบบอนันต์ เนื่องจากแต่ละการหดตัวหรือการลบจะลดจำนวนขอบและจุดยอดของกราฟ (จำนวนเต็มที่ไม่เป็นลบ) ^{[ 8 ]}ส่วนที่สำคัญของทฤษฎีบทนี้คือไม่มีแอนติเชนแบบอนันต์ ซึ่งเป็นเซตของกราฟแบบอนันต์ที่ไม่มีความสัมพันธ์กันโดยลำดับไมเนอร์ หากเป็นเซตของกราฟ และเป็นเซตย่อยของที่มีกราฟตัวแทนหนึ่งกราฟสำหรับแต่ละชั้นสมมูลขององค์ประกอบขั้นต่ำ (กราฟที่อยู่ในแต่ไม่มีไมเนอร์ที่เหมาะสมอยู่ใน) แล้วจะก่อให้เกิดแอนติเชน ดังนั้น วิธีที่เทียบเท่าในการกล่าวถึงทฤษฎีบทคือ ในเซตของกราฟแบบอนันต์ใดๆ จะต้องมีองค์ประกอบขั้นต่ำที่ไม่สมมาตรกันเพียงจำนวนจำกัดเท่านั้น ${\displaystyle {\mathcal {S}}}$${\displaystyle {\mathcal {M}}}$${\displaystyle {\mathcal {S}}}$${\displaystyle {\mathcal {S}}}$${\displaystyle {\mathcal {S}}}$${\displaystyle {\mathcal {M}}}$${\displaystyle {\mathcal {S}}}$

อีกรูปแบบหนึ่งที่เทียบเท่ากับทฤษฎีบทนี้คือ ในชุดกราฟอนันต์ใดๆ จะต้องมีกราฟคู่หนึ่งซึ่งกราฟหนึ่งเป็นไมเนอร์ของอีกกราฟหนึ่ง^{[ 8 ]}ข้อความที่ว่าทุกชุดอนันต์มีองค์ประกอบขั้นต่ำจำนวนจำกัดนั้นบ่งบอกถึงรูปแบบของทฤษฎีบทนี้ เพราะถ้ามีองค์ประกอบขั้นต่ำเพียงจำนวนจำกัด กราฟที่เหลือแต่ละกราฟจะต้องเป็นของคู่ประเภทนี้กับองค์ประกอบขั้นต่ำตัวใดตัวหนึ่ง และในทิศทางตรงกันข้าม รูปแบบของทฤษฎีบทนี้บ่งบอกถึงข้อความที่ว่าไม่มีแอนติเชนอนันต์ เพราะแอนติเชนอนันต์คือเซตที่ไม่มีคู่ใดๆ ที่เกี่ยวข้องกันด้วยความสัมพันธ์แบบไมเนอร์ ${\displaystyle {\mathcal {S}}}$

กล่าวกันว่าตระกูล ของกราฟ ปิดภายใต้การดำเนินการของการหาไมเนอร์ หากไมเนอร์ทุกตัวของกราฟในก็เป็นสมาชิกของ ด้วยเช่นกันถ้าเป็นตระกูลที่ปิดไมเนอร์แล้ว ให้เป็นคลาสของกราฟที่ไม่อยู่ใน( ส่วนเติมเต็มของ) ตามทฤษฎีบทของโรเบิร์ตสัน-เซย์มัวร์ จะมีเซตจำกัดขององค์ประกอบขั้นต่ำในองค์ประกอบขั้นต่ำเหล่านี้ก่อให้เกิดลักษณะเฉพาะของกราฟต้องห้ามของ: กราฟในคือกราฟที่ไม่มีกราฟใดในเป็นไมเนอร์^{[ 9 ]}สมาชิกของเรียกว่าไมเนอร์ที่ถูกยกเว้น (หรือไมเนอร์ต้องห้ามหรือสิ่งกีดขวางไมเนอร์ขั้นต่ำ ) สำหรับ ตระกูล${\displaystyle {\mathcal {F}}}$${\displaystyle {\mathcal {F}}}$${\displaystyle {\mathcal {F}}}$${\displaystyle {\mathcal {F}}}$${\displaystyle {\mathcal {S}}}$${\displaystyle {\mathcal {F}}}$${\displaystyle {\mathcal {F}}}$${\displaystyle {\mathcal {H}}}$${\displaystyle {\mathcal {S}}}$${\displaystyle {\mathcal {F}}}$${\displaystyle {\mathcal {F}}}$${\displaystyle {\mathcal {H}}}$${\displaystyle {\mathcal {H}}}$${\displaystyle {\mathcal {F}}}$

ตัวอย่างเช่นกราฟระนาบมีคุณสมบัติปิดภายใต้การหาไมเนอร์: การยุบขอบในกราฟระนาบ หรือการลบขอบหรือจุดยอดออกจากกราฟ ไม่สามารถทำลายคุณสมบัติความเป็นระนาบของกราฟได้ ดังนั้น กราฟระนาบจึงมีลักษณะเฉพาะของไมเนอร์ที่ต้องห้าม ซึ่งในกรณีนี้กำหนดโดยทฤษฎีบทของแวกเนอร์ : เซตของกราฟที่ไม่ใช่ระนาบที่มีไมเนอร์น้อยที่สุดประกอบด้วยกราฟเพียงสองกราฟเท่านั้น คือกราฟสมบูรณ์และกราฟสองส่วนสมบูรณ์และกราฟระนาบก็คือกราฟที่ไม่มีไมเนอร์อยู่ในเซตนั้น ${\displaystyle {\mathcal {H}}}$${\displaystyle K_{5}}$${\displaystyle K_{3,3}}$${\displaystyle {\mathcal {H}}=\{K_{5},K_{3,3}\}}$

การมีอยู่ของลักษณะเฉพาะของไมเนอร์ที่ต้องห้ามสำหรับตระกูลกราฟปิดไมเนอร์ทั้งหมด เป็นวิธีที่เทียบเท่ากับการกล่าวถึงทฤษฎีบทโรเบิร์ตสัน-เซย์มัวร์ สมมติว่าทุกตระกูลกราฟปิดไมเนอร์มีเซตจำกัดของไมเนอร์ที่ต้องห้ามขั้นต่ำ และให้เป็นเซตอนันต์ของกราฟใดๆ กำหนดจากเป็นตระกูลของกราฟที่ไม่มีไมเนอร์ในแล้วเป็นกราฟปิดไมเนอร์และมีเซตจำกัดของไมเนอร์ที่ต้องห้ามขั้นต่ำ ให้เป็นส่วนเติมเต็มของเป็นเซตย่อยของเนื่องจากและเป็น เซต ที่ไม่เกี่ยวข้องกัน และเป็นกราฟขั้นต่ำในพิจารณากราฟในไม่สามารถมีไมเนอร์ที่เหมาะสมใน ได้เนื่องจากเป็นกราฟขั้นต่ำในในขณะเดียวกันต้องมีไมเนอร์ในเนื่องจากมิฉะนั้นจะเป็นองค์ประกอบในดังนั้นเป็นองค์ประกอบใน กล่าว คือเป็นเซตย่อยของและกราฟอื่นๆ ทั้งหมดในมีไมเนอร์ในบรรดากราฟในดังนั้นเป็นเซตจำกัดขององค์ประกอบขั้นต่ำของ ${\displaystyle {\mathcal {F}}}$${\displaystyle {\mathcal {H}}}$${\displaystyle {\mathcal {S}}}$${\displaystyle {\mathcal {F}}}$${\displaystyle {\mathcal {S}}}$${\displaystyle {\mathcal {S}}}$${\displaystyle {\mathcal {F}}}$${\displaystyle {\mathcal {H}}}$${\displaystyle {\mathcal {C}}}$${\displaystyle {\mathcal {F}}}$${\displaystyle {\mathcal {S}}}$${\displaystyle {\mathcal {C}}}$${\displaystyle {\mathcal {S}}}$${\displaystyle {\mathcal {F}}}$${\displaystyle {\mathcal {H}}}$${\displaystyle {\mathcal {C}}}$${\displaystyle G}$${\displaystyle {\mathcal {H}}}$${\displaystyle G}$${\displaystyle {\mathcal {S}}}$${\displaystyle G}$${\displaystyle {\mathcal {C}}}$${\displaystyle G}$${\displaystyle S}$${\displaystyle G}$${\displaystyle {\mathcal {F}}}$${\displaystyle G}$${\displaystyle {\mathcal {S}}}$${\displaystyle {\mathcal {H}}}$${\displaystyle {\mathcal {S}}}$${\displaystyle {\mathcal {S}}}$${\displaystyle {\mathcal {H}}}$${\displaystyle {\mathcal {H}}}$${\displaystyle {\mathcal {S}}}$

เพื่อแสดงให้เห็นถึงทิศทางการสมมูลอีกด้านหนึ่ง สมมติว่าทุกเซตของกราฟมีเซตย่อยจำกัดของกราฟขั้นต่ำ และให้เซตที่ปิดด้วยไมเนอร์มา เราต้องการหาเซตของกราฟที่กราฟหนึ่งอยู่ในเซตนั้นก็ต่อเมื่อมันไม่มีไมเนอร์ใน เซตนั้น ให้เป็นกราฟที่ไม่ใช่ไมเนอร์ของกราฟใดๆ ในเซตนั้นและให้เป็นเซตจำกัดของกราฟขั้นต่ำในเซตนั้น ทีนี้ ให้กราฟหนึ่ง ใดๆ มา สมมติก่อนว่าอยู่ในเซตนั้นกราฟหนึ่งไม่สามารถมีไมเนอร์ในเซต นั้นได้ เนื่องจากอยู่ในเซตนั้นและเป็นเซตย่อยของเซตนั้นทีนี้ สมมติว่าไม่ได้อยู่ในเซตนั้น ดังนั้น กราฟหนึ่งจึงไม่ใช่ไมเนอร์ของกราฟใดๆ ในเซตนั้นเนื่องจากเป็นเซตที่ปิดด้วยไมเนอร์ ดังนั้นอยู่ใน เซต นั้น ดังนั้น จึงมีไมเนอร์ในเซตนั้น ${\displaystyle {\mathcal {F}}}$${\displaystyle {\mathcal {H}}}$${\displaystyle {\mathcal {F}}}$${\displaystyle {\mathcal {H}}}$${\displaystyle {\mathcal {E}}}$${\displaystyle {\mathcal {F}}}$${\displaystyle {\mathcal {H}}}$${\displaystyle {\mathcal {E}}}$${\displaystyle G}$${\displaystyle G}$${\displaystyle {\mathcal {F}}}$${\displaystyle G}$${\displaystyle {\mathcal {H}}}$${\displaystyle G}$${\displaystyle {\mathcal {F}}}$${\displaystyle {\mathcal {H}}}$${\displaystyle {\mathcal {E}}}$${\displaystyle G}$${\displaystyle {\mathcal {F}}}$${\displaystyle G}$${\displaystyle {\mathcal {F}}}$${\displaystyle {\mathcal {F}}}$${\displaystyle G}$${\displaystyle {\mathcal {E}}}$${\displaystyle G}$${\displaystyle {\mathcal {H}}}$

เซตของกราฟจำกัดต่อไปนี้เป็นเซตปิดไมเนอร์ และด้วยเหตุนี้ (ตามทฤษฎีบทโรเบิร์ตสัน-เซย์มัวร์) จึงมีลักษณะเฉพาะของไมเนอร์ที่ต้องห้าม:

• ป่า , ป่าเชิงเส้น ( การรวมกันแบบไม่ทับซ้อนของกราฟเส้นทาง ), ป่าเทียมและกราฟกระบองเพชร ;
• กราฟระนาบกราฟนอกระนาบกราฟยอด (ที่เกิดจากการเพิ่มจุดยอดเดียวให้กับกราฟระนาบ) กราฟทอรอยด์และกราฟที่สามารถฝัง บน แมนิโฟลด์สองมิติคงที่ใดๆ^ได้ [ ^{10 ]}
• กราฟที่สามารถฝังได้โดยไม่มีลิงก์ในปริภูมิยูคลิด 3 มิติ และกราฟที่ สามารถฝังได้ โดยไม่มีปมในปริภูมิยูคลิด 3 มิติ; ^{[ 10 ]}
• กราฟที่มีเซตจุดยอดป้อนกลับที่มีขนาดจำกัดโดยค่าคงที่ที่กำหนดไว้ กราฟที่มีค่าคงที่ของกราฟ Colin de Verdière จำกัดโดยค่าคงที่ที่กำหนดไว้ กราฟที่มีtreewidth , pathwidthหรือbranchwidthจำกัดโดยค่าคงที่ที่กำหนดไว้

ก่อนที่ทฤษฎีบทโรเบิร์ตสัน-เซย์มัวร์จะได้รับการพิสูจน์ ตัวอย่างของเซตสิ่งกีดขวางแบบจำกัดสำหรับกราฟบางประเภทนั้นเป็นที่รู้จักกันอยู่แล้ว ตัวอย่างเช่น สิ่งกีดขวางสำหรับเซตของป่าทั้งหมดคือ กราฟ วงวน (หรือถ้าจำกัดเฉพาะกราฟแบบง่ายก็คือวงจรที่มีสามจุดยอด) ซึ่งหมายความว่ากราฟจะเป็นป่าก็ต่อเมื่อไม่มีไมเนอร์ใดเป็นวงวน (หรือวงจรที่มีสามจุดยอด ตามลำดับ) สิ่งกีดขวางเพียงอย่างเดียวสำหรับเซตของเส้นทางคือต้นไม้ที่มีสี่จุดยอด โดยจุดยอดหนึ่งมีดีกรี 3 ในกรณีเหล่านี้ เซตสิ่งกีดขวางจะมีองค์ประกอบเพียงตัวเดียว แต่โดยทั่วไปแล้วจะไม่เป็นเช่นนั้นทฤษฎีบทของวากเนอร์กล่าวว่ากราฟจะเป็นกราฟระนาบก็ต่อเมื่อไม่มีหรือเป็นไมเนอร์ กล่าวอีกนัยหนึ่ง เซตเป็นเซตสิ่งกีดขวางสำหรับเซตของกราฟระนาบทั้งหมด และในความเป็นจริงเป็นเซตสิ่งกีดขวางขั้นต่ำที่ไม่ซ้ำกัน ทฤษฎีบทที่คล้ายกันกล่าวว่าและเป็นไมเนอร์ต้องห้ามสำหรับเซตของกราฟนอกระนาบ ${\displaystyle K_{5}}$${\displaystyle K_{3,3}}$${\displaystyle \{K_{5},K_{3,3}\}}$${\displaystyle K_{4}}$${\displaystyle K_{2,3}}$

แม้ว่าทฤษฎีบท Robertson–Seymour จะขยายผลลัพธ์เหล่านี้ไปยังตระกูลกราฟปิดไมเนอร์ใดๆ ก็ตาม แต่มันก็ไม่ใช่สิ่งทดแทนผลลัพธ์เหล่านี้ได้อย่างสมบูรณ์ เพราะมันไม่ได้ให้คำอธิบายที่ชัดเจนของเซตสิ่งกีดขวางสำหรับตระกูลใดๆ ตัวอย่างเช่น มันบอกเราว่าเซตของกราฟทอรอยดัลมีเซตสิ่งกีดขวางที่จำกัด แต่มันไม่ได้ให้เซตดังกล่าว เซตของไมเนอร์ต้องห้ามทั้งหมดสำหรับกราฟทอรอยดัลยังคงไม่เป็นที่รู้จัก แต่มีกราฟอย่างน้อย 17,535 กราฟ^{[ 11 ]}

ทฤษฎีบท Robertson–Seymour มีผลสำคัญต่อความซับซ้อนในการคำนวณ เนื่องจากการพิสูจน์โดย Robertson และ Seymour ว่าสำหรับกราฟที่กำหนดไว้แต่ละกราฟจะมี อัลกอริทึม เวลาพหุนามสำหรับการทดสอบว่ากราฟมีไมเนอร์หรือไม่ เวลาการทำงานของอัลกอริทึมนี้เป็นกำลังสาม (ตามขนาดของกราฟที่จะตรวจสอบ) แม้ว่าจะมีปัจจัยคงที่ที่ขึ้นอยู่กับขนาดของไมเนอร์ในระดับเหนือพหุนามก็ตามเวลาการทำงานได้รับการปรับปรุงให้เป็นกำลังสองโดย Kawarabayashi, Kobayashi และ Reed ^{[ 12 ]}ด้วยเหตุนี้ สำหรับตระกูลไมเนอร์ปิดทุกตระกูลจะมีอัลกอริทึมเวลาพหุนามสำหรับการทดสอบว่ากราฟอยู่ในตระกูลหรือไม่: ตรวจสอบว่ากราฟที่กำหนดมีไมเนอร์ต้องห้ามแต่ละอันในชุดสิ่งกีดขวางของหรือไม่^{[ 13 ]}${\displaystyle H}$${\displaystyle H}$${\displaystyle H}$${\displaystyle {\mathcal {F}}}$${\displaystyle {\mathcal {F}}}$${\displaystyle H}$${\displaystyle H}$${\displaystyle {\mathcal {F}}}$

อย่างไรก็ตาม วิธีนี้ต้องใช้ชุดสิ่งกีดขวางจำกัดเฉพาะในการทำงาน และทฤษฎีบทไม่ได้ให้ชุดดังกล่าว ทฤษฎีบทพิสูจน์ว่าชุดสิ่งกีดขวางจำกัดดังกล่าวมีอยู่จริง ดังนั้นปัญหาจึงเป็นพหุนามเนื่องจากอัลกอริทึมข้างต้น อย่างไรก็ตาม อัลกอริทึมนี้สามารถใช้งานได้จริงก็ต่อเมื่อมีการให้ชุดสิ่งกีดขวางจำกัดดังกล่าวเท่านั้น ผลก็คือ ทฤษฎีบทพิสูจน์ว่าปัญหานี้สามารถแก้ไขได้ในเวลาพหุนาม แต่ไม่ได้ให้อัลกอริทึมเวลาพหุนามที่เฉพาะเจาะจงสำหรับการแก้ปัญหา การพิสูจน์ความเป็นพหุนามดังกล่าวไม่ใช่แบบสร้างสรรค์ กล่าวคือ พิสูจน์ความเป็นพหุนามของปัญหาโดยไม่ให้อัลกอริทึมเวลาพหุนามที่ชัดเจน^{[ 14 ]}ในหลายกรณีเฉพาะ การตรวจสอบว่ากราฟอยู่ในตระกูลปิดไมเนอร์ที่กำหนดหรือไม่ สามารถทำได้อย่างมีประสิทธิภาพมากขึ้น เช่น การตรวจสอบว่ากราฟเป็นระนาบหรือไม่ สามารถทำได้ในเวลาเชิงเส้น

สำหรับค่าคงที่ของกราฟที่มีคุณสมบัติว่า สำหรับแต่ละค่า กราฟที่มีค่าคงที่ไม่เกินจะเป็นกราฟปิดไมเนอร์ วิธีการเดียวกันนี้สามารถนำมาใช้ได้ ตัวอย่างเช่น จากผลลัพธ์นี้ ความกว้างของต้นไม้ ความกว้างของกิ่ง และความกว้างของเส้นทาง การครอบคลุมของจุดยอดและจีนัสต่ำสุดของการฝังตัว ล้วนสามารถนำไปใช้กับวิธีการนี้ได้ และสำหรับค่าคงที่ใดๆจะมีอัลกอริทึมเวลาพหุนามสำหรับการทดสอบว่าค่าคงที่เหล่านี้ไม่เกิน หรือไม่โดยที่เลขชี้กำลังในเวลาการทำงานของอัลกอริทึมไม่ขึ้นอยู่กับ ปัญหาที่มีคุณสมบัตินี้ คือสามารถแก้ไขได้ในเวลาพหุนามสำหรับค่าคงที่ใดๆโดยมีเลขชี้กำลังที่ไม่ขึ้นอยู่กับเรียกว่า ปัญหา ที่สามารถแก้ไข ได้ ด้วย พารามิเตอร์คงที่${\displaystyle k}$${\displaystyle k}$${\displaystyle k}$${\displaystyle k}$${\displaystyle k}$${\displaystyle k}$${\displaystyle k}$

อย่างไรก็ตาม วิธีนี้ไม่ได้ให้ขั้นตอนวิธีแบบพารามิเตอร์คงที่ที่สามารถคำนวณค่าพารามิเตอร์สำหรับกราฟที่กำหนดโดยไม่ทราบค่าได้โดยตรงเนื่องจากความยากลำบากในการกำหนดชุดของไมเนอร์ต้องห้าม นอกจากนี้ ค่าคงที่จำนวนมากที่เกี่ยวข้องในผลลัพธ์เหล่านี้ทำให้ไม่สามารถนำไปใช้ได้จริง ดังนั้น การพัฒนาขั้นตอนวิธีแบบพารามิเตอร์คงที่ที่ชัดเจนสำหรับปัญหาเหล่านี้ โดยมีการพึ่งพาค่าที่ดีขึ้นจึงยังคงเป็นแนวทางการวิจัยที่สำคัญ ${\displaystyle k}$${\displaystyle k}$

Friedman , Robertson และ Seymour (1987) แสดงให้เห็นว่าทฤษฎีบทต่อไปนี้แสดงให้เห็นถึง ปรากฏการณ์ ความเป็นอิสระโดยไม่สามารถพิสูจน์ได้ในระบบที่เป็นทางการต่างๆ ที่แข็งแกร่งกว่าเลขคณิตของ Peano มาก แต่สามารถพิสูจน์ได้ ในระบบที่อ่อนแอกว่า ZFCมาก: ^{[ 15 ]}

ทฤษฎีบท : สำหรับจำนวนเต็มบวกทุกจำนวนจะมีจำนวนเต็มขนาดใหญ่มากจำนวนหนึ่ง ซึ่งถ้าเป็นลำดับของกราฟแบบไม่มีทิศทางจำกัด โดยแต่ละกราฟมีขนาดไม่เกินแล้วสำหรับบางจำนวน${\displaystyle n}$${\displaystyle m}$${\displaystyle G_{1},\dots ,G_{m}}$${\displaystyle G_{i}}$${\displaystyle n+i}$${\displaystyle G_{j}\leq G_{k}}$${\displaystyle j\leq k}$

(ในที่นี้ขนาดของกราฟคือจำนวนรวมของจุดยอดและขอบ และ ≤ หมายถึงลำดับย่อย)

ฟรีดแมนใช้ผลลัพธ์นี้กับกราฟย่อยลูกบาศก์อย่างง่ายเพื่อสร้างฟังก์ชันที่เติบโตอย่าง^{รวดเร็ว} SSCG [ ^{16 ]}

• ทฤษฎีบทโครงสร้างกราฟ

• ไวส์สไตน์, เอริค ดับเบิลยู. , "ทฤษฎีบทโรเบิร์ตสัน-เซย์มัวร์" , MathWorld