প্ল্যানার গ্রাফ ও অয়লারের সূত্র

১ · Planar Graph ও Euler's Formula

একটি planar graphPlanar Graphএমন একটি গ্রাফ যা সমতলে (২-মাত্রিক plane-এ) এমনভাবে আঁকা যায় যাতে কোনো দুটি edge একে অপরকে ক্রস না করে। হলো এমন একটি গ্রাফ যা সমতলে এমনভাবে আঁকা যায় যে কোনো দুটি edge একে অপরকে ক্রস করে না। যখন একটি planar graph এভাবে আঁকা হয়, এটি সমতলকে কয়েকটি অঞ্চলে ভাগ করে, প্রতিটিকে বলা হয় faceFaceএকটি planar drawing-এ edge দ্বারা ঘেরা একটি অঞ্চল, যার মধ্যে অসীম বিস্তৃত বাইরের (outer/unbounded) অঞ্চলটিও একটি face হিসেবে গণনা করা হয়। — এর মধ্যে অসীম বিস্তৃত বাইরের অঞ্চলটিকেও একটি face হিসেবে গণনা করা হয়।

২ · $E \leq 3n-6$ অসমতা ও $K_5$-এর Non-Planarity

একটি সহজ (simple, L18 দ্রষ্টব্য) planar graph-এ ($n \geq 3$ vertex নিয়ে), Euler's formula থেকে একটি গুরুত্বপূর্ণ উপরের সীমা (upper bound) বের করা যায়। প্রতিটি face অন্তত ৩টি edge দ্বারা ঘেরা থাকে (সরল গ্রাফে কোনো ২-edge face সম্ভব নয়), এবং প্রতিটি edge ঠিক ২টি face-এর সীমানায় থাকে। তাই সব face-এর "সীমানা-দৈর্ঘ্য" যোগ করলে পাওয়া যায় $2E$, যা কমপক্ষে $3F$ হতে হবে:

$$2E \geq 3F \implies F \leq \frac{2E}{3}$$

Euler's formula থেকে $F = 2 - V + E$। এটি বসিয়ে —

$$2 - V + E \leq \frac{2E}{3} \implies 6 - 3V + 3E \leq 2E \implies E \leq 3V - 6$$

import math

n = 5
e = math.comb(n, 2)          # K5-এ edge সংখ্যা
bound = 3 * n - 6            # planar হওয়ার জন্য সর্বোচ্চ অনুমোদিত edge

print(f"K5-এ vertex সংখ্যা, n = {n}")
print(f"K5-এ edge সংখ্যা, e = C(n,2) = {e}")
print(f"Planar হওয়ার জন্য ঊর্ধ্বসীমা, 3n-6 = {bound}")
print("K5 কি planar হতে পারে (e <= bound)?", e <= bound)

৩ · Kuratowski's Theorem

$K_5$ ছাড়াও আরেকটি বিখ্যাত non-planar গ্রাফ হলো $K_{3,3}$ (৩+৩ vertex-বিশিষ্ট complete bipartite graph, L18 দ্রষ্টব্য) — এটিও একইভাবে non-planar প্রমাণ করা যায় (bipartite গ্রাফে কোনো ত্রিভুজ (odd cycle) না থাকায় প্রতিটি face কমপক্ষে ৪-edge দৈর্ঘ্যের হতে হয়, যা একটি কঠোরতর সীমা $E \leq 2n-4$ দেয়; $K_{3,3}$-এর $E=9$, কিন্তু $2(6)-4=8 < 9$)।