Planar graph — Euler-এর সূত্র আর Kuratowski

১ · Planar graph আর plane drawing — কাটাকাটি ছাড়া আঁকা

বাজারঘর তিনটি নতুন গুদাম খুলছে। প্রতিটিতে পানি, গ্যাস আর বিদ্যুতের লাইন লাগবে, আর নিরাপত্তার কারণে মাটির নিচের কোনো দুটি লাইন একে অন্যকে কাটতে পারবে না (সবকিছু একই গভীরতায়)। নয়টি লাইন কি এভাবে বসানো যায়? কাগজে চেষ্টা করলে আটটি সহজে বসে, নবমটিতে এসে আটকে যায়। এটি বহু পুরোনো “তিন ইউটিলিটির ধাঁধা”। এই পর্বের শেষে আপনি শুধু উত্তর নয়, এর পূর্ণ প্রমাণও লিখতে পারবেন।

এই পর্বে graph মানে সসীম undirected graph; উপপাদ্যের শর্তে কোথায় simple graph লাগবে, তা আলাদা করে বলা আছে। মূল সংজ্ঞাগুলো পর্ব ৫৭ “গ্রাফ — সংজ্ঞা, degree আর handshake theorem”-এ।

পার্থক্যটি গুরুত্বপূর্ণ: planar হওয়া graph-এর ধর্ম, আর plane graph একটি নির্দিষ্ট ছবি। নিচের বাঁ দিকে K₄-এর পরিচিত ছবি: বর্গ আর দুটি কর্ণ, মাঝে একটি crossing. তবু K₄ planar, কারণ ডান দিকের মতো করে কাটাকাটি ছাড়াও আঁকা যায়। একটি ছবিতে crossing থাকলে কিছুই প্রমাণ হয় না; “planar নয়” দেখাতে হলে প্রমাণ করতে হয় যে কোনো ছবিতেই crossing এড়ানো যায় না।

ডান দিকের ছবিতে চারটি face, প্রতিটির degree 3 (বাইরের f4-এর সীমানা 1, 2, 3). যোগফল 3 + 3 + 3 + 3 = 12 = 2 × 6, edge-সংখ্যার ঠিক দ্বিগুণ। এটি কাকতালীয় নয়।

1. প্রতিটি edge-এর দুটি পাশ। প্রতিটি পাশ ঠিক একটি face-এর সীমানা-হাঁটায় একবার আসে। — আঁকার গঠন
2. দুই পাশে দুটি আলাদা face হলে edge-টি দুই face-এ একবার করে গোনা হয়; একই face হলে সেই face-এ দুবার। দুই ক্ষেত্রেই edge-টির অবদান ঠিক 2. — সংজ্ঞায় দুবার গোনার নিয়ম
3. সব edge-এর অবদান যোগ করলে ∑ deg(f) = 2e. ∎ — পর্ব ৩৭-এর double counting

এটি vertex-এর handshake lemma-র হুবহু “face-রূপ”, আর পরের প্রতিটি সীমার মূল হাতিয়ার। একটি প্রয়োজনীয় তথ্য আমরা প্রমাণ ছাড়া ব্যবহার করব: সমতলে আঁকা প্রতিটি বন্ধ বক্ররেখা (যেমন একটি cycle-এর ছবি) সমতলকে ঠিক দুই ভাগে ভাগ করে, ভেতর আর বাইরে। এটি Jordan curve theorem; কথাটি স্বজ্ঞায় স্পষ্ট, কিন্তু সাধারণ বক্ররেখার জন্য এর কঠোর প্রমাণ topology-র কাজ, তাই এখানে বাদ।

২ · Euler-এর সূত্র v − e + f = 2 — প্রমাণ আর যাচাই

K₄-এ 4 − 6 + 4 = 2. একটি ঘনকের ছবিতে ৮টি কোণ, ১২টি ধার, ৬টি তল: 8 − 12 + 6 = 2. একটি একা cycle C_n-এ n − n + 2 = 2 (ভেতর আর বাইরে)। প্রতিবার ২. এর কারণ নিচের উপপাদ্য।

প্রমাণের আগে একটি লেমা, যা পর্ব ৫৯-এর ফল থেকে সরাসরি আসে।

1. Cycle নেই, তাই পর্ব ৫৯-এর উপপাদ্য ৪.২ অনুযায়ী প্রতিটি edge একটি bridge. একটি edge সরালে component ঠিক ১ বাড়ে (একটি edge বড়জোর দুটি component জোড়ে, আর bridge সরালে বাড়েই)। — bridge ⇔ কোনো cycle-এ নেই
2. Edge সরালে নতুন cycle তৈরি হয় না, তাই বাকি সব edge তখনো bridge. একটি একটি করে সব e-টি edge সরালে component 1 থেকে 1 + e হয়। কিন্তু শেষে কোনো edge নেই, তাই component = v. সুতরাং v = 1 + e. — পুনরাবৃত্তি
3. একটি face-এর সীমানা আলাদা করে আরেকটি অঞ্চল ঘিরতে হলে একটি বন্ধ রেখা লাগে, আর graph-এর বন্ধ রেখা মানে একটি cycle. Cycle নেই, তাই পুরো সমতল একটিই face: f = 1. ∎ — Jordan curve theorem-এর স্বজ্ঞা

এমন graph-ই tree, যার পূর্ণ আলোচনা মডিউল ১১-এর পর্ব ৬৫ “Tree — ধর্ম, rooted tree আর m-ary tree-এর হিসাব”-এ। এখন মূল প্রমাণ।

উপপাদ্য ২.১-এর প্রমাণ (e-এর ওপর strong induction, পর্ব ১১): দাবি P(e): “e-টি edge-এর প্রতিটি connected plane graph-এ v − e + f = 2”.

1. ধরুন e-এর চেয়ে কম edge-এর সব connected plane graph-এ সূত্রটি সত্য। এখন e-টি edge-এর যেকোনো connected plane graph G নিন। — inductive hypothesis
2. ক্ষেত্র ক: G-তে কোনো cycle নেই। লেমা ২.২ অনুযায়ী e = v − 1 আর f = 1, তাই v − (v − 1) + 1 = 2. (e = 0, অর্থাৎ একটি মাত্র vertex, এই ক্ষেত্রেরই অংশ: 1 − 0 + 1 = 2.) — ভিত্তি
3. ক্ষেত্র খ: G-তে একটি cycle C আছে। C-এর একটি edge x নিন। C-এর ছবি সমতলকে ভেতর আর বাইরে ভাগ করে, তাই x-এর এক পাশের face C-এর ভেতরে আর অন্য পাশের face বাইরে: দুটি আলাদা face. — Jordan curve theorem
4. x একটি cycle-এ আছে, তাই bridge নয়, আর G − x তখনো connected. — পর্ব ৫৯, উপপাদ্য ৪.২
5. x মুছলে তার দুই পাশের দুটি face এক হয়ে যায়, বাকি face অপরিবর্তিত। তাই G − x-এ v′ = v, e′ = e − 1, f′ = f − 1. — গণনা
6. G − x-এর edge e − 1টি, তাই inductive hypothesis অনুযায়ী v − (e − 1) + (f − 1) = 2, অর্থাৎ v − e + f = 2. ∎

দুটি সূক্ষ্ম জায়গা লক্ষ করুন। এক, ধাপ ৩-এ মুছতে হয় একটি cycle-এর edge; যেকোনো edge মুছলে graph ভেঙে যেতে পারে (bridge), তখন hypothesis খাটে না, আর f-ও কমে না। দুই, induction-এর দিক: আমরা যেকোনো বড় G থেকে শুরু করে ছোটটিতে নেমেছি। উল্টো পথে “ছোট graph-এ একটি edge যোগ করে সব বড় graph পাওয়া যায়” ধরে নেওয়া graph-এর induction-এর পরিচিত ভুল (পর্ব ৫৯-এর অনুশীলন ৪ দেখুন)।

দুটি অনুসিদ্ধান্ত। (১) একই connected planar graph-কে যেভাবেই কাটাকাটি ছাড়া আঁকুন, face-এর সংখ্যা f = e − v + 2, অর্থাৎ আঁকার ওপর নির্ভর করে না। (২) G-তে c-টি component থাকলে v − e + f = 1 + c: প্রতিটি component আলাদাভাবে সূত্র মানে, কিন্তু বাইরের face সবার একটিই, তাই c-টি সূত্র যোগ করলে বাইরের face c বার না গুনে একবার গুনতে হয়, যোগফল 2c − (c − 1) = c + 1. AI সহকারী প্রায়ই disconnected graph-এও সোজা “= 2” বসিয়ে দেয়; শর্তটি লক্ষ রাখুন।

এবার যন্ত্রে যাচাই। নিচের ব্লক সোজা-রেখার কয়েকটি আঁকা বানায়, আর face সত্যিই গুনে বের করে, কোনো সূত্র বসিয়ে নয়। কৌশলটির নাম rotation system: প্রতিটি vertex-এর প্রতিবেশীদের কোণ অনুযায়ী ঘড়ির কাঁটার ক্রমে সাজানো হয়, তারপর একটি “edge-এর দিক” থেকে শুরু করে প্রতিটি vertex-এ পরের প্রতিবেশীতে ঘুরে একটি face-এর সীমানা ধরে হাঁটা হয়। যতবার নতুন হাঁটা শুরু করতে হয়, ততগুলো face. প্রথমবার চালালে ব্রাউজারে Python (Pyodide) নামতে কয়েক সেকেন্ড লাগে।

import math, random
def faces(pos, edges):                   # count faces of a straight-line drawing
    adj = {v: [] for v in pos}
    for u, v in edges:
        adj[u].append(v); adj[v].append(u)
    for v in adj:                        # rotation system: neighbours sorted by angle
        adj[v].sort(key=lambda w: math.atan2(pos[w][1] - pos[v][1], pos[w][0] - pos[v][0]))
    seen, f = set(), 0
    for u in adj:
        for v in adj[u]:
            if (u, v) in seen: continue
            f += 1; a, b = u, v          # walk once around a new face
            while (a, b) not in seen:
                seen.add((a, b)); nb = adj[b]
                a, b = b, nb[(nb.index(a) - 1) % len(nb)]
    return f
def grid(a, b):
    pos = {(i, j): (i, j) for i in range(a) for j in range(b)}
    E = [((i, j), (i + 1, j)) for i in range(a - 1) for j in range(b)]
    return pos, E + [((i, j), (i, j + 1)) for i in range(a) for j in range(b - 1)]
def wheel(n):
    pos = {k: (math.cos(2 * math.pi * k / n), math.sin(2 * math.pi * k / n)) for k in range(n)}
    return pos | {'hub': (0, 0)}, [(k, (k + 1) % n) for k in range(n)] + [('hub', k) for k in range(n)]
def stacked(k, rnd):                     # k times: new point inside a random triangle
    pos, E, tris = {0: (0, 0), 1: (10, 0), 2: (5, 9)}, [(0, 1), (1, 2), (2, 0)], [(0, 1, 2)]
    for v in range(3, 3 + k):
        a, b, c = tris.pop(rnd.randrange(len(tris)))
        pos[v] = tuple((pos[a][i] + pos[b][i] + pos[c][i]) / 3 for i in (0, 1))
        E += [(v, a), (v, b), (v, c)]; tris += [(a, b, v), (b, c, v), (a, c, v)]
    return pos, E
rnd = random.Random(62)
for name, (pos, E) in [('grid 3x4', grid(3, 4)), ('wheel W8', wheel(8)),
                       ('stack 9', stacked(6, rnd)), ('stack 40', stacked(37, rnd))]:
    v, e, f = len(pos), len(E), faces(pos, E)
    print(f'{name:9} v={v:2} e={e:3} f={f:2}  v-e+f={v - e + f}  3v-6={3 * v - 6}')

grid 3x4  v=12 e= 17 f= 7  v-e+f=2  3v-6=30
wheel W8  v= 9 e= 16 f= 9  v-e+f=2  3v-6=21
stack 9   v= 9 e= 21 f=14  v-e+f=2  3v-6=21
stack 40  v=40 e=114 f=76  v-e+f=2  3v-6=114

৩ · Edge-এর সীমা: e ≤ 3v − 6 আর e ≤ 2v − 4

Euler-এর সূত্রে v আর e জানা থাকলে f জানা যায়। লেমা ১.৩-এর সঙ্গে মেলালে একটি শক্তিশালী সীমা বের হয়: planar graph-এ edge বেশি থাকতে পারে না।

1. প্রথমে ধরুন G connected, আর একটি plane drawing নিন। v ≥ 3, তাই e ≥ 2. Simple graph-এ loop নেই (দৈর্ঘ্য ১-এর face অসম্ভব), parallel edge নেই (দৈর্ঘ্য ২-এর face অসম্ভব), আর একটি মাত্র edge-এর graph (যার একমাত্র face-এর degree 2) এখানে বাদ। তাই প্রতিটি face-এর degree ≥ 3. — simple, v ≥ 3
2. লেমা ১.৩: 2e = ∑ deg(f) ≥ 3f, তাই f ≤ 2e/3. — face-এর handshake
3. Euler: 2 = v − e + f ≤ v − e + 2e/3 = v − e/3, অর্থাৎ e ≤ 3v − 6. সমতা মানে ধাপ ২-এ সমতা, অর্থাৎ প্রতিটি face-এর degree ঠিক 3. — উপপাদ্য ২.১
4. G connected না হলে: প্রতিটি component-এর বাইরের face-এর সীমানার একটি vertex থেকে পরের component-এর এমন একটি vertex-এ কাটাকাটি ছাড়াই একটি নতুন edge টানা যায় (component-গুলো পাশাপাশি আঁকুন)। এতে G planar আর simple থাকে, e শুধু বাড়ে, আর connected graph-টির জন্য ধাপ ১–৩ খাটে। ∎

অনুসিদ্ধান্ত: K₅ planar নয়। v = 5, e = C(5, 2) = 10, অথচ 3v − 6 = 9. সীমা ভাঙে, তাই কোনো plane drawing নেই। লক্ষ করুন যুক্তির ধরন: “আঁকার চেষ্টা করে পারিনি” নয়, বরং “থাকলে Euler আর face-এর handshake মিলে 10 ≤ 9 দাঁড়াত”।

Graph-এ ত্রিভুজ না থাকলে প্রতিটি face অন্তত চার edge দিয়ে ঘেরা, তাই সীমা আরও কড়া হয়। সাধারণভাবে, graph-এর সবচেয়ে ছোট cycle-এর দৈর্ঘ্যকে বলে girth g.

1. Connected ক্ষেত্রে (বাকিটা উপপাদ্য ৩.১-এর ধাপ ৪-এর মতো): G-তে cycle আছে, তাই প্রতিটি face-এর সীমানায় একটি cycle থাকে, যার দৈর্ঘ্য ≥ g; ফলে deg(f) ≥ g. (যে face-এর সীমানায় cycle নেই, তা শুধু cycle-হীন graph-এ সম্ভব।) — girth-এর সংজ্ঞা
2. 2e ≥ g · f, তাই f ≤ 2e/g. Euler: 2 ≤ v − e + 2e/g, অর্থাৎ e(g − 2)/g ≤ v − 2. — উপপাদ্য ২.১
3. সাজালে e ≤ g(v − 2)/(g − 2). ত্রিভুজ না থাকলে g ≥ 4, আর ডান পাশ g বাড়লে কমে, তাই e ≤ 4(v − 2)/2 = 2v − 4. ∎ (g = 3 দিলে 3v − 6, উপপাদ্য ৩.১।)

অনুসিদ্ধান্ত: K_3,3 planar নয়, আর তিন ইউটিলিটির ধাঁধার উত্তর “অসম্ভব”। তিনটি গুদাম আর তিনটি ইউটিলিটি, প্রতিটি গুদাম প্রতিটি ইউটিলিটির সঙ্গে: ঠিক K_3,3. এটি bipartite, আর bipartite graph-এ কোনো বিজোড় cycle নেই (পর্ব ৫৭), তাই ত্রিভুজও নেই। নিচের stepper পুরো যুক্তিটি সংখ্যা দিয়ে চালায়।

নিচের ব্লক এই সীমাগুলোকে একটি দ্রুত ছাঁকনি হিসেবে চালায়। Girth বের হয় প্রতিটি vertex থেকে BFS করে: BFS-এ একটি “পেছনের” edge {x, y} পেলে দুটি শাখা জুড়ে dist(x) + dist(y) + 1 দৈর্ঘ্যের একটি বন্ধ হাঁটা পাওয়া যায়, আর সব শুরুর বিন্দু মিলিয়ে সবচেয়ে ছোটটি girth. Graph-গুলোর সঙ্গে Q₃ (ঘনক) আর Petersen graph-ও আছে।

from fractions import Fraction
def graph(edges):
    adj = {}
    for u, v in edges:
        adj.setdefault(u, set()).add(v); adj.setdefault(v, set()).add(u)
    return adj
def girth(adj):                          # shortest cycle, BFS from every vertex
    best = None
    for s in adj:
        dist, par, q = {s: 0}, {s: None}, [s]
        for x in q:
            for y in adj[x]:
                if y not in dist:
                    dist[y], par[y] = dist[x] + 1, x; q.append(y)
                elif par[x] != y:
                    L = dist[x] + dist[y] + 1
                    best = L if best is None else min(best, L)
    return best
K = lambda n: [(i, j) for i in range(n) for j in range(i + 1, n)]
K33 = [(a, b) for a in 'ABC' for b in 'xyz']
petersen = [(i, (i + 1) % 5) for i in range(5)] + [(i, i + 5) for i in range(5)] \
         + [(5 + i, 5 + (i + 2) % 5) for i in range(5)]
Q3 = [(a, b) for a in range(8) for b in range(a + 1, 8) if bin(a ^ b).count('1') == 1]
tests = {'K4': K(4), 'K5': K(5), 'K5 - edge': K(5)[1:], 'K3,3': K33,
         'K3,3 + leaf': K33 + [('z', 'L')], 'Q3': Q3, 'Petersen': petersen}
for name, E in tests.items():
    adj = graph(E); v, e, g = len(adj), len(E), girth(adj)
    bound = Fraction(g * (v - 2), g - 2)            # e <= g(v-2)/(g-2), v >= 3
    verdict = 'NOT planar (proved)' if e > bound else 'passes: no conclusion'
    print(f'{name:12} v={v:2} e={e:2} girth={g} 3v-6={3*v-6:2} bound={float(bound):5.2f}  {verdict}')

K4           v= 4 e= 6 girth=3 3v-6= 6 bound= 6.00  passes: no conclusion
K5           v= 5 e=10 girth=3 3v-6= 9 bound= 9.00  NOT planar (proved)
K5 - edge    v= 5 e= 9 girth=3 3v-6= 9 bound= 9.00  passes: no conclusion
K3,3         v= 6 e= 9 girth=4 3v-6=12 bound= 8.00  NOT planar (proved)
K3,3 + leaf  v= 7 e=10 girth=4 3v-6=15 bound=10.00  passes: no conclusion
Q3           v= 8 e=12 girth=4 3v-6=18 bound=12.00  passes: no conclusion
Petersen     v=10 e=15 girth=5 3v-6=24 bound=13.33  NOT planar (proved)

৪ · প্রতিটি planar graph-এ degree ≤ 5-এর একটি vertex

e ≤ 3v − 6 বলে planar graph-এ edge “গড়ে” কম। Handshake lemma দিয়ে কথাটি vertex-এর ভাষায় আনা যায়, আর পর্ব ৬৩-এর রং করার প্রমাণগুলো ঠিক এই তথ্যের ওপর দাঁড়িয়ে।

1. v ≤ 2 হলে প্রতিটি degree ≤ 1, কাজ শেষ। ধরুন v ≥ 3. — ছোট ক্ষেত্র
2. বিরোধের জন্য ধরুন প্রতিটি vertex-এর degree ≥ 6. Handshake lemma: 2e = ∑ deg(v) ≥ 6v, তাই e ≥ 3v. — handshake lemma
3. কিন্তু উপপাদ্য ৩.১ অনুযায়ী e ≤ 3v − 6 < 3v. বিরোধ। ∎

একই হিসাব আরও বেশি বলে: গড় degree 2e/v ≤ 6 − 12/v < 6. সীমা 5 নিখুঁত: icosahedron (২০টি ত্রিভুজ-তলের ঘনবস্তু)-এর graph planar আর প্রতিটি vertex-এর degree ঠিক 5 (v = 12, e = 30 = 3 · 12 − 6). তাই “degree ≤ 4-এর vertex সবসময় আছে” মিথ্যা; §৯-এ এই মিথ্যা দাবির একটি “প্রমাণ” ধরা হবে।

প্রয়োগের ঝলক: ছয় রঙের উপপাদ্য। v-এর ওপর induction: যেকোনো simple planar G-তে degree ≤ 5-এর একটি vertex x নিন, G − x (এখনো planar) কে inductive hypothesis দিয়ে ৬ রঙে রং করুন, তারপর x-এর বড়জোর ৫টি প্রতিবেশী বড়জোর ৫টি রং নেয়, তাই x-এর জন্য একটি রং বাকি থাকে। Induction আবার সঠিক দিকে: যেকোনো বড় graph থেকে একটি vertex সরিয়ে নামা। পাঁচ আর চার রঙের অনেক গভীর গল্প পর্ব ৬৩ “Graph coloring — chromatic number, scheduling আর চার রঙের উপপাদ্য”-এ।

৫ · Kuratowski-এর উপপাদ্য — non-planar graph-এর সম্পূর্ণ চরিত্র

সীমাগুলো কিছু graph ধরে, সব নয়। আসল প্রশ্ন: planar নয় এমন প্রতিটি graph-এর ভেতরে কি কোনো একটি “দোষী” কাঠামো আছে? উত্তর হ্যাঁ, আর দোষী মাত্র দুটি: K₅ আর K_3,3, একটু ছদ্মবেশে।

Subdivision ছবির কিছুই বদলায় না: একটি রেখার মাঝে একটি বিন্দু আঁকা মাত্র। তাই G planar ⇔ G-এর যেকোনো subdivision planar. আর planar graph-এর প্রতিটি subgraph planar (ছবি থেকে কিছু মুছে দিলে কাটাকাটি তৈরি হয় না)। এই দুটি মিলিয়ে সহজ দিকটি প্রমাণ হয়ে যায়: G-এর ভেতরে K₅ বা K_3,3-এর কোনো subdivision subgraph হিসেবে থাকলে G planar হতে পারে না, কারণ তা হলে সেই subdivision, আর তাই K₅ বা K_3,3, planar হতো। কঠিন দিকটি একটি বিখ্যাত উপপাদ্য।

কঠিন দিকের (“K₅ বা K_3,3-এর subdivision না থাকলে planar”) প্রমাণ কয়েক পাতার, সাধারণত connectivity-র ওপর induction আর কয়েকটি ক্ষেত্র-বিশ্লেষণ দিয়ে করা হয়; এখানে বাদ রাখা হলো, graph theory-র মানসম্মত পাঠ্যবইয়ে (যেমন Diestel বা West-এর বই) পাবেন। একটি সমতুল্য রূপ Klaus Wagner ১৯৩৭ সালে দেন, যাতে subdivision-এর জায়গায় minor: কিছু vertex আর edge মুছে আর কিছু edge সংকুচিত করে (edge contraction, যা পর্ব ৪৩-এর Karger-এর algorithm-এ দেখেছেন) যে graph পাওয়া যায়।

Petersen graph দুটি রূপের পার্থক্য সুন্দরভাবে দেখায়। বাইরের পাঁচভুজ 0–4, ভেতরের তারা 5–9, আর পাঁচটি “স্পোক” i–(i + 5). পাঁচটি স্পোক সংকুচিত করলে প্রতিটি নতুন vertex i বাইরের i ± 1 আর তারার i ± 2-এর সঙ্গে যুক্ত, অর্থাৎ বাকি চারজনের সবার সঙ্গে: K₅, তাই K₅ একটি minor. অথচ K₅-এর কোনো subdivision Petersen-এর ভেতরে নেই, কারণ তার জন্য degree ≥ 4-এর পাঁচটি vertex লাগত, আর Petersen-এর সব degree 3. Kuratowski-এর রূপে দোষী তাই K_3,3-এর একটি subdivision. নিচে একটি সত্যিকারের planarity-পরীক্ষক দিয়ে সেটি খুঁজে বের করা হলো।

সত্যিকারের run. NetworkX 3.7 (BSD লাইসেন্স) আর CPython 3.12.13 দিয়ে একটি ছোট প্রজেক্টে নিচের স্ক্রিপ্ট চালানো হয়েছে। check_planarity(G, counterexample=True) planar না হলে একটি Kuratowski subgraph ফেরত দেয়; আমরা তার degree গুনে দেখি সেটি কোন ধরনের।

~/bazarghar-dm$ cat kuratowski_check.py   # মূল অংশ
for name, G in graphs.items():
    ok, cert = nx.check_planarity(G, counterexample=True)
    ...  # planar হলে faces = 2 - v + e, না হলে cert-এর degree-তালিকা
P = nx.petersen_graph()          # outer 0-4, inner 5-9, spokes i -- i+5
for i in range(5):
    P = nx.contracted_nodes(P, i, i + 5, self_loops=False)

~/bazarghar-dm$ uv run python kuratowski_check.py
K5: NOT planar; Kuratowski subgraph v=5 e=10 degrees=[4, 4, 4, 4, 4]
K3,3: NOT planar; Kuratowski subgraph v=6 e=9 degrees=[3, 3, 3, 3, 3, 3]
Petersen: NOT planar; Kuratowski subgraph v=9 e=12 degrees=[2, 2, 2, 3, 3, 3, 3, 3, 3]
Q3: planar, v=8 e=12 faces=6
icosahedron: planar, v=12 e=30 faces=20
Petersen, 5 spokes contracted: 5 vertices, 10 edges, is K5: True

Planarity কত দ্রুত পরীক্ষা করা যায়? সব subgraph-এ Kuratowski-কাঠামো খোঁজা সূচকীয় সময়ের কাজ। কিন্তু John Hopcroft আর Robert Tarjan ১৯৭৪ সালে দেখান যে DFS-ভিত্তিক একটি algorithm রৈখিক সময়ে, O(v) ধাপে, planarity ঠিক করতে পারে বলে উল্লেখ করা হয় (DFS-এর কোড DSA কোর্সের পর্ব ৪১-এ)। লক্ষ করুন, planar graph-এ e ≤ 3v − 6, তাই O(v + e) আর O(v) একই কথা। পরে আরও সহজ রৈখিক algorithm এসেছে; NetworkX-এর নথিপত্র অনুযায়ী এটি “left-right” planarity test ব্যবহার করে।

৬ · Dual graph — face হয়ে যায় vertex

মানচিত্রের প্রশ্ন সাধারণত জেলা নিয়ে, সীমানার মোড় নিয়ে নয়: কোন দুটি জেলা পাশাপাশি? এই প্রশ্নের graph হলো dual.

সংজ্ঞা থেকে সরাসরি: connected G-এর জন্য v* = f, e* = e, আর (G* নিজে plane graph বলে, আর প্রমাণ এখানে বাদ রেখে) f* = v. G*-এ একটি face-vertex-এর degree = সেই face-এর degree, তাই লেমা ১.৩ আসলে G*-এর সাধারণ handshake lemma. Euler-এর সূত্র dual-এ গেলেও অক্ষত: v* − e* + f* = f − e + v = 2.

দুটি সতর্কতা। এক, dual নির্ভর করে আঁকার ওপর: একই planar graph-এর দুটি আলাদা plane drawing-এর dual non-isomorphic হতে পারে, কারণ face-গুলোর সীমানা বদলে যায়। দুই, dual-এর ভাষায় পুরোনো সীমা নতুন সীমা দেয়: G-এ প্রতিটি vertex-এর degree ≥ 3 হলে G*-এর প্রতিটি face-এর degree ≥ 3, তাই উপপাদ্য ৩.১-এর যুক্তি G*-এ চালালে e ≤ 3f − 6. মানচিত্রের রং করার সমস্যাও এভাবে আসে: পাশাপাশি জেলায় ভিন্ন রং দেওয়া মানে dual graph-এর vertex রং করা। এই অনুবাদই চার রঙের উপপাদ্যকে graph theory-র প্রশ্ন বানিয়েছে (পর্ব ৬৩)।

৭ · Platonic solid — কেন ঠিক পাঁচটি

একটি উত্তল ঘনবস্তুর (convex polyhedron) একটি তলের ঠিক ওপরে চোখ রেখে তাকালে বাকি সব কোণ আর ধার সেই তলের ভেতরে কাটাকাটি ছাড়া দেখা যায় (এই ছবিকে Schlegel diagram বলে)। তাই প্রতিটি উত্তল ঘনবস্তুর কোণ আর ধার একটি connected plane graph, যার face হলো তলগুলো, আর Euler-এর সূত্র ঘনবস্তুর জন্যও খাটে: কোণ − ধার + তল = 2. ইতিহাসে সূত্রটি এই রূপেই প্রথম এসেছিল।

1. Face-এর handshake: pf = 2e. Vertex-এর handshake: qv = 2e. তাই f = 2e/p, v = 2e/q. — লেমা ১.৩ আর handshake lemma
2. Euler-এ বসালে 2e/q − e + 2e/p = 2. দুই পাশকে 2e দিয়ে ভাগ করলে 1/q + 1/p − 1/2 = 1/e. — উপপাদ্য ২.১
3. e > 0, তাই 1/p + 1/q > 1/2. গুণ করে সাজালে 2p + 2q > pq, অর্থাৎ (p − 2)(q − 2) < 4. — বীজগণিত
4. p − 2 আর q − 2 ধনাত্মক পূর্ণসংখ্যা, গুণফল 1, 2 বা 3: (1,1), (1,2), (2,1), (1,3), (3,1). অর্থাৎ (p, q) = (3,3), (3,4), (4,3), (3,5), (5,3). — সব ক্ষেত্র গোনা
5. প্রতিটির জন্য 1/e = 1/p + 1/q − 1/2 থেকে e, তারপর v আর f. পাঁচটিই সত্যিই ঘনবস্তু হিসেবে আছে: tetrahedron, octahedron, cube, icosahedron, dodecahedron. ∎

এই প্রমাণ একটি “গণনার” উপপাদ্য: graph-এর সম্ভাব্য ধরন পাঁচটির বেশি নয়। প্রতিটি ধরনের ঘনবস্তু যে জ্যামিতিকভাবে একটিই (আকার বাদে), সেটি আলাদা জ্যামিতিক যুক্তি, যা এখানে বাদ। সীমান্তের ক্ষেত্রগুলোও শিক্ষণীয়: (4, 4), (3, 6), (6, 3)-এ 1/p + 1/q = 1/2 ঠিক, অর্থাৎ “e অসীম”: এগুলো সমতলের বর্গ, ত্রিভুজ আর ষড়ভুজের টাইলস, যা কখনো বন্ধ হয় না।

1p = 3, q = 32p = 3, q = 43p = 3, q = 54p = 3, q ≥ 65p = 4, q = 3, 46p = 5, q = 3, 47p ≥ 6

নিচের ব্লক একই খোঁজ ভগ্নাংশে (fractions) চালায়, যাতে দশমিকের গোলমাল না হয়, আর তারপর একটি দ্বিতীয় প্রশ্ন করে: প্রতিটি কোণে ৩টি ধার আর তল শুধু পঞ্চভুজ আর ষড়ভুজ হলে পঞ্চভুজ কয়টি?

from fractions import Fraction as Fr
names = {(3, 3): 'tetrahedron', (3, 4): 'octahedron', (4, 3): 'cube',
         (3, 5): 'icosahedron', (5, 3): 'dodecahedron'}
for p in range(3, 9):                    # p = sides of every face
    for q in range(3, 9):                # q = edges at every vertex
        s = Fr(1, p) + Fr(1, q) - Fr(1, 2)           # Euler: s = 1/e
        if s <= 0: continue
        e = 1 / s; v, f = 2 * e / q, 2 * e / p
        print(f'(p,q)=({p},{q})  v={v} e={e} f={f}  v-e+f={v - e + f}  {names[(p, q)]}')
print('searched 3 <= p, q <= 8: only 5 pairs')
for h in (0, 20, 30):                    # 3-regular polyhedron, pentagons + hexagons
    for pent in range(60):
        e = Fr(5 * pent + 6 * h, 2); v = 2 * e / 3
        if v - e + pent + h == 2:
            print(f'hexagons={h:2} -> pentagons={pent}, v={v}, e={e}')

(p,q)=(3,3)  v=4 e=6 f=4  v-e+f=2  tetrahedron
(p,q)=(3,4)  v=6 e=12 f=8  v-e+f=2  octahedron
(p,q)=(3,5)  v=12 e=30 f=20  v-e+f=2  icosahedron
(p,q)=(4,3)  v=8 e=12 f=6  v-e+f=2  cube
(p,q)=(5,3)  v=20 e=30 f=12  v-e+f=2  dodecahedron
searched 3 <= p, q <= 8: only 5 pairs
hexagons= 0 -> pentagons=12, v=20, e=30
hexagons=20 -> pentagons=12, v=60, e=90
hexagons=30 -> pentagons=12, v=80, e=120

৮ · Crossing number আর বাস্তব প্রয়োগ

K_3,3 planar নয়, কিন্তু stepper-এ একটি crossing-এই আঁকা গেল। Non-planar graph কতটা “non-planar”, তার মাপ:

1. cr(G) = k crossing-এর একটি আঁকা নিন। প্রতিটি crossing-এ জড়িত দুটি edge-এর একটি মুছে দিন। বড়জোর k-টি edge মুছেছে, আর বাকি আঁকায় কোনো crossing নেই। — প্রতি crossing-এ একটি edge
2. বাকি graph planar, simple আর v ≥ 3, তাই তার edge ≤ 3v − 6. অর্থাৎ e − k ≤ 3v − 6, k ≥ e − 3v + 6. ∎ — উপপাদ্য ৩.১

K₅-এ সীমা 10 − 9 = 1, আর এক crossing-এর আঁকা আছে (K₄-এর plane drawing-এর বাইরে পঞ্চম vertex বসিয়ে), তাই cr(K₅) = 1. K_3,3-এ ত্রিভুজহীন রূপ ব্যবহার করুন: cr ≥ e − (2v − 4) = 9 − 8 = 1, আর stepper-এর ছবি দেখায় 1-এ হয়, তাই cr(K_3,3) = 1. K₆-এ সীমা 15 − 12 = 3, আর জানা আছে যে cr(K₆) = 3. তবে সাধারণভাবে এই সীমা দুর্বল: বড় K_n-এ আসল crossing number n⁴-এর মাত্রায় বাড়ে, অথচ সীমাটি কেবল n²-এর মাত্রায়।

প্রয়োগ।

• সার্কিট বোর্ড: এক স্তরের printed circuit board-এ তামার দুটি পথ কাটলে শর্ট সার্কিট। সংযোগের graph planar হলে এক স্তরেই নকশা সম্ভব; না হলে অন্য স্তরে যেতে “via” (স্তর পার হওয়ার ছিদ্র) লাগে, আর crossing number মোটামুটি বলে কতগুলো এমন পারাপার এড়ানো যাবে না। Chip নকশাতেও (VLSI) একই ধরনের প্রশ্ন আসে।
• মানচিত্র আর রাস্তা: রাজনৈতিক মানচিত্রের dual সবসময় planar (সীমানা কাটাকাটি করে না)। কিন্তু রাস্তার নেটওয়ার্ক planar না-ও হতে পারে: ঢাকার একটি flyover নিচের রাস্তাকে মোড় ছাড়াই পার হয়, যা graph-এ একটি crossing, কোনো vertex নয়। তাই বাজারঘরের রাইডার-রুটের মডেলে flyover থাকলে planar graph-এর উপপাদ্য অন্ধভাবে খাটানো চলবে না।
• ছবি আঁকা (graph drawing): মেট্রোর মানচিত্র বা নেটওয়ার্কের ডায়াগ্রাম পড়তে সহজ হয় crossing কম হলে, তাই আঁকার সফটওয়্যার crossing কমানোর চেষ্টা করে; সর্বনিম্ন খোঁজা সাধারণভাবে NP-hard বলে জানা যায়।
• তিন ইউটিলিটি: সমতলে বা গোলকে অসম্ভব (§৩)। কিন্তু একটি মগের মতো হাতলওয়ালা তলে (torus) K_3,3 এমনকি K₅-ও কাটাকাটি ছাড়া আঁকা যায়: “planar” প্রশ্নটি তলের আকারের ওপর নির্ভর করে।

৯ · পরীক্ষার অঙ্ক আর একটি ভুল প্রমাণ

অঙ্ক ১: Face গোনা

একটি connected plane graph-এ ১০টি vertex, প্রতিটির degree 3. কয়টি edge আর কয়টি face? (এমন graph আছে, যেমন পঞ্চভুজাকার prism: দুটি পঞ্চভুজ আর তাদের মিলিয়ে পাঁচটি খাড়া ধার।)

1. Handshake: 2e = 10 × 3 = 30, তাই e = 15.
2. Euler: f = 2 − v + e = 2 − 10 + 15 = 7 (prism-এ দুটি পঞ্চভুজ আর পাঁচটি চতুর্ভুজ)।

অঙ্ক ২: সর্বোচ্চ edge

(ক) ২০টি vertex-এর simple planar graph-এ সর্বোচ্চ কয়টি edge? (খ) ত্রিভুজ না থাকলে? (গ) ২০টি vertex আর ৫৫টি edge-এর planar simple graph কি সম্ভব?

1. (ক) 3 × 20 − 6 = 54, আর triangulation-এ ঠিক 54 পাওয়া যায় (§২-এর ব্লকের মতো ত্রিভুজের ভেতরে বিন্দু বসিয়ে)।
2. (খ) 2 × 20 − 4 = 36.
3. (গ) না: 55 > 54, উপপাদ্য ৩.১ ভাঙে।

অঙ্ক ৩: ফুটবলের ১২টি পঞ্চভুজ

একটি উত্তল ঘনবস্তুর প্রতিটি কোণে ঠিক ৩টি ধার, আর তল শুধু পঞ্চভুজ (p-টি) আর ষড়ভুজ (h-টি)। প্রমাণ করুন p = 12.

1. Vertex-এর handshake: 3v = 2e. Face-এর handshake: 5p + 6h = 2e. — দুই দিকের double counting
2. Euler: v − e + (p + h) = 2. 6 দিয়ে গুণ করে 6v = 4e বসালে 4e − 6e + 6p + 6h = 12, অর্থাৎ 6p + 6h − 2e = 12.
3. 2e = 5p + 6h বসালে 6p + 6h − 5p − 6h = 12, অর্থাৎ p = 12, h যা-ই হোক। ∎

প্রমাণের ভুল ধরুন: “প্রতিটি planar graph-এ degree ≤ 4-এর vertex আছে”

একজন লিখলেন: “v-এর ওপর induction. v ≤ 5-এ প্রতিটি degree ≤ 4, সত্য। ধরুন v-vertex-এর প্রতিটি simple planar graph-এ degree ≤ 4-এর একটি vertex আছে। এমন একটি graph H নিন, আর তার বাইরের face-এ একটি নতুন vertex x বসিয়ে কয়েকটি vertex-এর সঙ্গে জুড়ুন, যাতে graph planar থাকে। H-এর degree ≤ 4-এর vertex-টি হয় তখনো তাই থাকে, নয়তো x নিজেই কম degree-র, কারণ বাইরের face-এর সীমানায় বেশি vertex নেই। সুতরাং (v + 1)-vertex graph-এ দাবি সত্য। ∎”

ভুল কোথায়: প্রথমত দাবিটিই মিথ্যা: icosahedron-এর graph planar, ১২টি vertex, আর প্রতিটির degree 5 (scratch-এ NetworkX দিয়ে planarity আর degree মেলানো)। এবার দেখুন প্রমাণ ঠিক কোথায় ভাঙে। Icosahedron থেকে একটি vertex x সরালে ১১-vertex-এর একটি planar graph H থাকে, যাতে x-এর পাঁচ প্রতিবেশীর degree 4: H দাবি মানে। x ফেরত দিলে x ঠিক ওই পাঁচজনের সঙ্গে যুক্ত হয়, তাদের প্রত্যেকের degree 5 হয়ে যায়, আর x-এর নিজের degree-ও 5. অর্থাৎ “H-এর কম degree-র vertex তখনো তাই থাকে, নয়তো x নিজেই কম degree-র” ধাপটি প্রমাণহীন দাবি, আর এখানেই মিথ্যা। গভীরতর সমস্যা induction-এর ধরন: একটি ছোট graph-এ vertex যোগ করে নির্দিষ্ট ধরনের বড় graph বানালে সব বড় graph-এর কথা বলা হয় না। সঠিক পদ্ধতি সবসময়: যেকোনো (v + 1)-vertex graph থেকে শুরু করে একটি vertex সরিয়ে নামা, আর তারপর ফেরত দেওয়ার ধাপটি সত্যিই প্রমাণ করা, ঠিক যেমন §৪-এর ছয় রঙের প্রমাণে।

১০ · AI-এর যুগে — planarity-র প্রমাণ আর হিসাব যাচাই

Planar graph-এর প্রশ্নে AI সহকারী সূত্রগুলো প্রায় সবসময় সঠিক লেখে, কিন্তু শর্ত বাদ দেয় আর আবশ্যিক শর্তকে যথেষ্ট বলে চালিয়ে দেয়। কয়েকটি নিয়মিত ভুল আর ধরার উপায়:

AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট

• Graph simple আর connected কি না, আর v ≥ 3 কি না, লেখা আছে
• “Planar নয়” দাবির পেছনে একটি ভাঙা সীমা বা একটি স্পষ্ট Kuratowski subdivision আছে
• “Planar” দাবির পেছনে একটি আঁকা আছে, শুধু সীমা মানা নয়
• v − e + f-এর হিসাব নিজে মিলিয়েছি, disconnected হলে 1 + c ব্যবহার করেছি
• ছোট graph-এ check_planarity বা §২-এর face-গণনা দিয়ে উত্তর মিলিয়েছি
• উদ্ধৃত নাম, সাল আর উৎস বিশ্বস্ত পাঠ্যবইয়ে মিলিয়েছি

Planarity-র দাবি যাচাইয়ের সুবিধা: “না”-উত্তরের একটি প্রমাণপত্র (Kuratowski subgraph) আর “হ্যাঁ”-উত্তরের একটি প্রমাণপত্র (একটি plane drawing) দুটোই হাতে মিলিয়ে দেখা যায়। AI যে উত্তরই দিক, তার প্রমাণপত্র চেয়ে নিন।