درجه ی رئوس

درجه ی رأس $v$ در یک گراف بی جهت برابر است با تعداد یال هایی است که با آن رأس برخورد دارند به جز حلقه ها که، سهم یک حلقه در درجه ی یک رأس برابر ۲ می باشد. برای درک بهتر مطلب به مثال زیر توجه فرمایید:
مثال: درجه ی هر یک از رئوس گراف های زیر را بیابید. $$In \quad G : deg(a) = 2, deg(b) = 4, deg(c) = 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(c) = 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).$$