Tietze's graph
گراف تھیوری کے ریاضیاتی میدان میں، ٹیٹز کا گراف ایک غیر ہدایت شدہ کیوبک گراف ہے جس میں 12 عمودی اور 18 کنارے ہیں۔ اس کا نام ہینرچ فرانز فریڈرک ٹیٹز کے نام پر رکھا گیا ہے، جس نے 1910 میں دکھایا تھا کہ موبیئس پٹی کو چھ خطوں میں تقسیم کیا جا سکتا ہے جو سب ایک دوسرے کو چھوتے ہیں-تین پٹی کی حدود کے ساتھ اور تین اس کی مرکزی لکیر کے ساتھ-اور اس وجہ سے وہ گراف جو موبیئس پٹی پر سرایت کر چکے ہیں ان کے لیے چھ رنگوں کی ضرورت پڑ سکتی ہے۔ ٹیٹزے کی ذیلی تقسیم کے علاقوں کے سرحدی حصے (بشمول خود موبیئس پٹی کی حدود کے ساتھ والے حصے) ٹیٹزے کے گراف کا ایک سرایت بناتے ہیں۔ پیٹرسن گراف سے تعلق ٹیٹز کے گراف کو پیٹرسن گراف سے اس کے ایک عمودی حصے کو مثلث سے تبدیل کر کے بنایا جا سکتا ہے۔ ٹیٹز گراف کی طرح، پیٹرسن گراف چھ باہمی چھونے والے علاقوں کی حد بناتا ہے، لیکن موبیئس پٹی کے بجائے پروجیکٹو سطح پر۔ اگر کوئی پروجیکٹو طیارہ کے اس ذیلی حصے سے ایک سوراخ کاٹتا ہے، جو ایک ہی سرے کے گرد ہوتا ہے، تو گھیرے ہوئے سرے کو سوراخ کے ارد گرد خطے کی حدود کے مثلث سے تبدیل کر دیا جاتا ہے، جس سے ٹیٹز گراف کی پہلے بیان کردہ تعمیر ملتی ہے۔ ہیملٹنسیٹی ٹیٹز کا گراف اور پیٹرسن گراف دونوں زیادہ سے زیادہ غیر ہیملٹنین ہیں: ان کا کوئی ہیملٹنین سائیکل نہیں ہے، لیکن کسی بھی دو غیر ملحقہ عمودی حصوں کو ہیملٹنین راستے سے جوڑا جا سکتا ہے۔ ٹیٹز کا گراف اور پیٹرسن گراف صرف 2-ورٹیکس سے منسلک کیوبک غیر ہیملٹنین گراف ہیں جن میں 12 یا اس سے کم عمودی ہیں۔ پیٹرسن گراف کے برعکس، ٹیٹز کا گراف ہائپوہیملٹنین نہیں ہے: اس کے تین مثلث عمودی میں سے ایک کو ہٹانے سے ایک چھوٹا گراف بنتا ہے جو غیر ہیملٹنین رہتا ہے۔ ایج کلرنگ اور کامل ملاپ ایج کلرنگ ٹیٹز کے گراف کے لیے چار رنگوں کی ضرورت ہوتی ہے ؛ یعنی اس کا کرومیٹک انڈیکس 4 ہے۔ اسی طرح، ٹیٹز کے گراف کے کناروں کو چار مماثلتوں میں تقسیم کیا جا سکتا ہے، لیکن اس سے کم نہیں۔ ٹیٹز کا گراف اسنارک کی تعریف کے حصے سے ملتا جلتا ہے: یہ ایک کیوبک برج لیس گراف ہے جو 3 کنارے پر رنگین نہیں ہے۔ تاہم، زیادہ تر مصنفین اسنارکس کو 3 چکروں کے بغیر گراف تک محدود رکھتے ہیں، لہذا ٹیٹز کے گراف کو عام طور پر اسنارک نہیں سمجھا جاتا ہے۔ اس کے باوجود، یہ گراف J3 کے لیے آئسومورفک ہے، جو پھولوں کے اسنارکس کے ایک لامحدود خاندان کا حصہ ہے جسے 1975 میں آر آئزک نے متعارف کرایا تھا۔ پیٹرسن گراف کے برعکس، ٹیٹز گراف کا احاطہ چار کامل ملاپ سے کیا جا سکتا ہے۔ یہ خاصیت اس ثبوت میں کلیدی کردار ادا کرتی ہے کہ آیا گراف کو چار کامل ملاپ سے کور کیا جا سکتا ہے، یہ جانچنا این پی مکمل ہے۔ اضافی خصوصیات ٹیٹز کے گراف میں کرومیٹک نمبر 3، کرومیٹک انڈیکس 4، گرتھ 3 اور قطر 3 ہے۔ آزادی نمبر 5 ہے۔ اس کے آٹومورفزم گروپ کی ترتیب 12 ہے، اور یہ ڈائیڈرل گروپ D6 کے لیے آئسومورفک ہے، جو کہ ایک ہیکساگون کی ہم آہنگی کا گروپ ہے، جس میں گردش اور عکاسی دونوں شامل ہیں۔ اس گروپ کے عمودی حصوں پر سائز 3 اور سائز 6 کے دو مدار ہیں، اور اس طرح یہ گراف عمودی-عارضی نہیں ہے۔ گیلری بھی دیکھیں ڈیورر گراف اور فرینکلن گراف، دو دیگر 12-ورٹیکس کیوبک گراف نوٹ انفرادی گراف باقاعدہ گراف