גרף (תורת הגרפים) – הבדלי גרסאות

ה'''סדרת הדרגותדרגה''' <math>d(v)</math> של גרףצומת <math>v</math> בגרף '''<math>G=\left(V, E\right)</math>''' היא מספר הקשתות בגרף המכילות את <math>v</math>. '''סדרת הדרגות''' של גרף עם <math>n</math> צמתים וסדר <math>v_1,...,v_n</math> של הצמתים היא הסדרה <math>d(G)=\left(d(v_1),...,d(v_n)\right)</math> כאשר <math>d(v_i)</math> היא הדרגה של צומת <math>v_i</math>. סדרה נקראת '''גרפית''' אם היא סדרת הדרגות של איזשהו גרף. קיים אפיון של הסדרות הגרפיות ([[פאול ארדש|Erdős]] and Gallai, 1960<ref>{{צ-מאמר|מחבר=P. Erdős, T. Gallai|שם=Graphs with prescribed degrees of vertices|כתב עת=Mat. Lopak|כרך=11|עמ=264-274|שנת הוצאה=1960}}</ref>) המוביל לאלגוריתם פולינומיאלי להחלטה האם סדרה נתונה היא גרפית.