(Локальної) Ступенем або (валентністю)
![Ступені вершин графа (граф кратних ребер) Ступені вершин графа](https://images-on-off.com/images/114/stepenivershingrafa-c70fa1f7.png)
Якщо не обмовляється особливо, то петля враховується двічі при підрахунку валентності вершини.
Граф називається правильним (з валентністю r) або r-валентним графом (регулярним, однорідним), якщо ступеня всіх його вершин рівні.
Вершина називається ізольованою. якщо вона несуміжних ні з однією з вершин графа, або, що те ж саме, неінціндентна жодному ребру. Ступінь цієї вершини дорівнює 0.
Вершина, що має ступінь, рівну 1, називається висячої (кінцевий). Ребро, інціндентное висячої вершині, називають кінцевим.
Твердження 1. (Лемман рукостискання): У н-графі сума ступенів усіх вершин дорівнює подвоєному числу ребер (тобто парна):
![Ступені вершин графа (вершин) Ступені вершин графа](https://images-on-off.com/images/114/stepenivershingrafa-eb720b43.png)
Слідство 1. Довільний граф має парне число вершин непарного ступеня.
Слідство 1. Число ребер у повному графі одно
![Ступені вершин графа (граф кратних ребер) Ступені вершин графа](https://images-on-off.com/images/114/stepenivershingrafa-62d7dd2d.png)
В ор-графі дві (локальних) ступеня вершини:
![Ступені вершин графа (взаємно однозначно відповідає орієнтований) Ступені вершин графа](https://images-on-off.com/images/114/stepenivershingrafa-6c204eda.png)
![Ступені вершин графа (взаємно однозначно відповідає) Ступені вершин графа](https://images-on-off.com/images/114/stepenivershingrafa-6f326ef8.png)
Твердження 2. Суми ступенів усіх вершин ор-графа дорівнюють кількості ребер цього графа і, отже, рівні між собою:. m - число ребер.
Частини, суграфом і підграфи
Граф H називається частиною графа G (
![Ступені вершин графа (графа) Ступені вершин графа](https://images-on-off.com/images/114/stepenivershingrafa-12ac7c94.png)
Якщо безлічі вершин частини графа H і графа G збігаються:, то графH називається суграфом графа G. суграфом H називається покриває для н-графа G. якщо будь-яка вершина графа G інціндентна хоча б одному ребру з Н. (Тобто якщо граф G не має ізольованих вершин, то і суграфом покриває так само не повинен мати ізольованих вершин).
подграфом
![Ступені вершин графа (ступеня) Ступені вершин графа](https://images-on-off.com/images/114/stepenivershingrafa-0b061475.png)
![Ступені вершин графа (ступеня) Ступені вершин графа](https://images-on-off.com/images/114/stepenivershingrafa-9e7d6cf3.png)
![Ступені вершин графа (граф кратних ребер) Ступені вершин графа](https://images-on-off.com/images/114/stepenivershingrafa-1cc32fad.png)
![Ступені вершин графа (графа) Ступені вершин графа](https://images-on-off.com/images/114/stepenivershingrafa-4718b98f.png)
(Подграф
![Ступені вершин графа (вершин) Ступені вершин графа](https://images-on-off.com/images/114/stepenivershingrafa-2be50dc8.png)
![Ступені вершин графа (взаємно однозначно відповідає орієнтований) Ступені вершин графа](https://images-on-off.com/images/114/stepenivershingrafa-d9645fbf.png)
![Ступені вершин графа (взаємно однозначно відповідає орієнтований) Ступені вершин графа](https://images-on-off.com/images/114/stepenivershingrafa-e6462978.png)
Операції над частинами графа
доповнення
![Ступені вершин графа (вершин) Ступені вершин графа](https://images-on-off.com/images/114/stepenivershingrafa-fca92122.png)
, ;
сума
![Ступені вершин графа (вершин) Ступені вершин графа](https://images-on-off.com/images/114/stepenivershingrafa-affc082a.png)
![Ступені вершин графа (вершин) Ступені вершин графа](https://images-on-off.com/images/114/stepenivershingrafa-6e71b2b3.png)
![Ступені вершин графа (граф кратних ребер) Ступені вершин графа](https://images-on-off.com/images/114/stepenivershingrafa-efc51b11.png)
твір
![Ступені вершин графа (ступеня) Ступені вершин графа](https://images-on-off.com/images/114/stepenivershingrafa-8c82c2d6.png)
![Ступені вершин графа (ступеня) Ступені вершин графа](https://images-on-off.com/images/114/stepenivershingrafa-2bd3b3c1.png)
![Ступені вершин графа (взаємно однозначно відповідає) Ступені вершин графа](https://images-on-off.com/images/114/stepenivershingrafa-810f8f81.png)
частини
![Ступені вершин графа (граф кратних ребер) Ступені вершин графа](https://images-on-off.com/images/114/stepenivershingrafa-29fcabcc.png)
![Ступені вершин графа (взаємно однозначно відповідає орієнтований) Ступені вершин графа](https://images-on-off.com/images/114/stepenivershingrafa-9e4fcded.png)
, .
частини
![Ступені вершин графа (графа) Ступені вершин графа](https://images-on-off.com/images/114/stepenivershingrafa-3b4f98ff.png)
![Ступені вершин графа (взаємно однозначно відповідає орієнтований) Ступені вершин графа](https://images-on-off.com/images/114/stepenivershingrafa-150eb720.png)
.
Якщо, то сума
![Ступені вершин графа (графа) Ступені вершин графа](https://images-on-off.com/images/114/stepenivershingrafa-66b541e5.png)
Графи і бінарні відносини
Відношенню R, заданому на множині V, взаємно однозначно відповідає орієнтований граф G (R) без кратних ребер з безліччю вершин V, в якому ребро
![Ступені вершин графа (взаємно однозначно відповідає орієнтований) Ступені вершин графа](https://images-on-off.com/images/114/stepenivershingrafa-2d48e68f.png)
![Ступені вершин графа (взаємно однозначно відповідає орієнтований) Ступені вершин графа](https://images-on-off.com/images/114/stepenivershingrafa-3fce2ee3.png)
![Ступені вершин графа (вершин) Ступені вершин графа](https://images-on-off.com/images/114/stepenivershingrafa-853170ac.png)
![Ступені вершин графа (взаємно однозначно відповідає) Ступені вершин графа](https://images-on-off.com/images/114/stepenivershingrafa-85f9d8bc.png)
![Ступені вершин графа (взаємно однозначно відповідає) Ступені вершин графа](https://images-on-off.com/images/114/stepenivershingrafa-e12c13c0.png)
![Ступені вершин графа (графа) Ступені вершин графа](https://images-on-off.com/images/114/stepenivershingrafa-dfa14613.png)
![Ступені вершин графа (вершин) Ступені вершин графа](https://images-on-off.com/images/114/stepenivershingrafa-8d3bdaee.png)
![Ступені вершин графа (ступеня) Ступені вершин графа](https://images-on-off.com/images/114/stepenivershingrafa-3242c0f3.png)
Граф G (
![Ступені вершин графа (ступеня) Ступені вершин графа](https://images-on-off.com/images/114/stepenivershingrafa-017f4ae0.png)
![Ступені вершин графа (взаємно однозначно відповідає орієнтований) Ступені вершин графа](https://images-on-off.com/images/114/stepenivershingrafa-d6d4ad41.png)
Граф зворотного відносини G (
![Ступені вершин графа (взаємно однозначно відповідає орієнтований) Ступені вершин графа](https://images-on-off.com/images/114/stepenivershingrafa-30c6f9f0.png)
Граф об'єднання двох відносин, заданих на V,
![Ступені вершин графа (ступеня) Ступені вершин графа](https://images-on-off.com/images/114/stepenivershingrafa-32017533.png)
![Ступені вершин графа (вершин) Ступені вершин графа](https://images-on-off.com/images/114/stepenivershingrafa-85511a2b.png)
![Ступені вершин графа (граф кратних ребер) Ступені вершин графа](https://images-on-off.com/images/114/stepenivershingrafa-8f9af421.png)
.
Граф перетину відносин на V,
![Ступені вершин графа (вершин) Ступені вершин графа](https://images-on-off.com/images/114/stepenivershingrafa-b3c5a010.png)
![Ступені вершин графа (графа) Ступені вершин графа](https://images-on-off.com/images/114/stepenivershingrafa-f6ae1350.png)
![Ступені вершин графа (граф кратних ребер) Ступені вершин графа](https://images-on-off.com/images/114/stepenivershingrafa-0ecbb721.png)
.