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

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

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

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