درخت و گراف مسطح

این کارگاه تکمیلی است و در کتاب‌های درسی افغانستان نیامده است. درخت گرافی همبند و بدون دور است. ویژگی‌های آن: میان هر دو رأس دقیقاً یک مسیر هست؛ درختی با n رأس دقیقاً ⁦n − 1⁩ یال دارد؛ درختی با بیشتر از یک رأس دست‌کم یک برگ (رأسی از درجهٔ ۱) دارد. درخت برای نشان دادن شجره‌نامه، فهرست مطالب و مسابقه‌های حذفی به کار می‌رود.

درخت فراگیر یک گراف همبند، بخشی از آن است که همهٔ رأس‌ها را دارد و درخت است. برای ساختن آن از گرافی با V رأس و E یال، تعداد ⁦E − (V − 1)⁩ یال را برمی‌داریم، از هر دور یک یال.

گراف مسطح گرافی است که آن را بدون تقاطع یال‌ها کشیده می‌توانیم. برای گراف مسطح همبند فرمول اویلر برقرار است: ⁦V − E + F = 2⁩، که F تعداد ناحیه‌هاست و ناحیهٔ بیرونی هم در آن شمرده می‌شود. این مطلب در سطح بالاتر است.