همبندی، مسیر، دور و رسم بدون برداشتن قلم

این کارگاه تکمیلی است و در کتاب‌های درسی افغانستان نیامده است. بعد از رأس، یال و درجه، این مفهوم‌ها می‌آیند: مسیر (دنباله‌یی از یال‌ها که هر یال از جایی شروع می‌شود که یال قبلی تمام شده)، دور (مسیری که به رأس شروع برمی‌گردد) و همبندی (هر دو رأس با یک مسیر به هم وصل‌اند). هر گراف به چند «مؤلفهٔ همبند» تقسیم می‌شود.

مسیر اویلری هر یال را دقیقاً یک بار می‌پیماید. این مسیر وقتی هست که گراف همبند باشد و صفر یا دو رأس طاق داشته باشد. اگر صفر باشد، دور اویلری هم هست؛ اگر دو باشد، مسیر از یکی از آن دو شروع و به دیگری تمام می‌شود. با همین، مسئلهٔ پل‌های کونیگسبرگ (چهار رأس طاق) و سؤال «شکل را بدون برداشتن قلم می‌شود کشید؟» جواب داده می‌شود.

اشتباه‌های معمول: رأسِ تنها را یک مؤلفه حساب نکردن؛ برای درجه، رأس‌ها را به‌جای یال‌ها شمردن؛ و فکر کردن به اینکه هر شکلی را می‌شود با یک خط کشید.