Liczba łuków w grafie skierowanym. Fgt: Jaka jest liczba łuków w grafie skierowanym o N wierzchołkach, gdzie sumaryczny stopień każdego wierzchołka v jest równy in(v) + out(v) = 4, jeśli taki graf istnieje? In i out są stopniami wejściowymi i wyjściowymi wierzchołka v.

wredulus_pospolitus: Przyjmujemy, że nie może być pętli (wejściowy nie może być jednocześnie wyjściowym łukiem). Należy zauważyć, że każdy 'wyjściowy' łuk z jakiegokolwiek wierzchołka będzie 'wejściowym' dla innego wierzchołka Co można zapisać jako ∑in(v_i) = ∑out(v_i) gdzie v_i reprezentuje kolejne wierzchołki (uwaga −−− to nie oznacza że in(v_i) = out(v_i)) wiemy że dla każdego i zachodzi: in(v_i) + out(v_i) = 4 Więc ∑in(v_i) + ∑out(v_i) = 4v stąd: ∑in(v_i) = ∑out(v_i) = 2v <−−− tyle masz łuków