درخت؛
میان هر دو رأس فقط یک مسیر نگه دار

تعریف اصلی را دو بخشی بنویس

برای درخت‌بودن، همبندی و بدون‌دوربودن هر دو لازم‌اند. گراف بدون دور اما چندجزئی جنگل است، و گراف همبندِ دارای دور نیز درخت نیست.

رابطهٔ رأس و یال را شرط‌دار استفاده کن

هر درخت با n رأس، n−1 یال دارد. اما فقط شمردن n−1 یال بدون بررسی ساختار همیشه کافی نیست؛ همراه با همبندی یا بدون‌دوربودن شرط مناسب را به کار ببر.

برگ را از درجهٔ یک بشناس

رأسی با درجهٔ یک برگ نام دارد. درخت دارای بیش از یک رأس دست‌کم دو برگ دارد. رأس تنها در درخت یک‌رأسی را مطابق قرارداد تعریف درس تحلیل کن و نتیجهٔ درخت‌های بزرگ‌تر را بی‌شرط به آن تعمیم نده.

حذف هر یال درخت را قطع می‌کند

چون میان دو سوی هر یال مسیر جایگزین وجود ندارد، حذف یک یال درخت تعداد اجزای همبند را افزایش می‌دهد. پس همهٔ یال‌های درخت پل‌اند.

افزودن یک یال یک دور یکتا می‌سازد

میان دو رأس درخت پیش‌تر یک مسیر یکتا وجود دارد. افزودن یال مستقیم تازه میان آن‌ها، همان مسیر و یال جدید را به یک دور تبدیل می‌کند. این ویژگی برای اصلاح گراف و ساخت درخت فراگیر مفید است.

نمونهٔ تشخیص با شمارش

گرافی همبند با ۸ رأس و ۷ یال یک درخت است. اگر با همان ۸ رأس و همبندی، ۸ یال داشته باشد، دست‌کم یک دور وجود دارد و درخت نیست.

درخت فراگیر همهٔ رأس‌ها را نگه می‌دارد

درخت فراگیر زیرگرافی است که همهٔ رأس‌های گراف اصلی را دارد، همبند است و دور ندارد. لازم نیست همهٔ یال‌های گراف اصلی را نگه دارد؛ دقیقاً تعداد لازم برای اتصال بدون دور باقی می‌ماند.

از گراف همبند با حذف یال‌های دور بساز

تا وقتی دور وجود دارد، یک یال از دور را حذف کن به‌گونه‌ای که همبندی حفظ شود. روند را تا رسیدن به n−1 یال ادامه بده. حذف پل مجاز نیست چون گراف را جدا می‌کند.

از رأس‌ها با افزودن یال امن بساز

می‌توان با زیرگرافی بدون یال آغاز و یال‌هایی افزود که دو جزء متفاوت را به هم وصل کنند. اگر دو رأس از قبل در یک جزء باشند، افزودن یال میان آن‌ها دور می‌سازد.

کنترل نهایی با سه آزمون

همهٔ رأس‌های اصلی حضور دارند؟ زیرگراف همبند است؟ تعداد یال‌ها n−1 و دوری وجود ندارد؟ برای مبانی از گراف و برای پل‌ها و پیمایش از مسیر اویلری کمک بگیر.