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

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

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

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