درجه‌ی رئوس

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

برای درک بهتر مطلب به مثال زیر توجه فرمایید: مثال: درجه‌ی هر یک از رئوس گراف‌های زیر را بیابید. $$In \quad G : deg(a) = 2, deg(b) = 4, deg© = 4, deg(d) = 1, deg(e) = 3, deg(f) = 4, deg(g) = 0$$ $$In \quad H : deg(a) = 4, deg(b) = 4+2* = 6, deg© = 1, deg(d) = 5, deg(e) = 6$$ (سهم حلقه در درجه‌ی رئوس ۲ می‌باشد.)

اگر $G(V, E)$ یک گراف بی‌جهت (چه چندگانه، چه ساده و چه با حلقه) با $m$ یال باشد آنگاه $$2m = \sum_{v \in V}deg(v).$$ پس از این رابطه می‌توان نتیجه گرفت که تعداد رئوس با درجه‌ی فرد، زوج است.

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

اگر $G(V, E)$ یک گراف جهت‌دار باشد آنگاه $$|m| = \sum_{v \in V}deg^-(v) + \sum_{v \in V}deg^+(v).$$