Комплетан граф

У грани математике, теорији графова, комплетан граф или потпун граф је прост^[1] граф код кога између свака два чвора постоји грана. Комплетан граф са n чворова у ознаци има

Комплетан граф
, комплетан граф са 7 чворова
Чворови
Гране

${\displaystyle {n \choose 2}={\frac {n(n-1)}{2}}}$

гране. Комплетан граф је регуларан граф^[2], и сваки његов чвор има степен Комплемент комплетног графа је празан граф (граф без грана). У матричној репрезентацији, комплетном графу одговара матрица чији сви елементи су јединице.

Комплетан граф је такође клика. У ствари, проблем клике се дефинише као проблем проналажења највећег комплетног подграфа неког графа.

Следе цртежи комплетних графова са од 1 до 8 чворова, са назначеним бројем грана.

${\displaystyle K_{1}:0}$	${\displaystyle K_{2}:1}$	${\displaystyle K_{3}:3}$	${\displaystyle K_{4}:6}$
${\displaystyle K_{5}:10}$	${\displaystyle K_{6}:15}$	${\displaystyle K_{7}:21}$	${\displaystyle K_{8}:28}$