Podaj stopień minimalny oraz liczbę krawędzi w grafie poaw: X = {1,2,3, ..., 9} G = (V, E) V − zbiór wszystkich 3−elem. pozdbiorów zbioru X (wyliczyłem, że jest ich 84. 9 po 3) E − zbiór krawędzi takich, że u,v ∊ E ⇔ |u ∩ v| = 1 Ile wynosi stopień minimalny w tym grafie? Ile ten graf ma krawędzi? Czy graf jest dwudzielny? Prosiłbym o jakieś proste wyjaśnienie. Pozdrawiam.

Adamm:

	6 2
biorąc konkretny wierzchołek 'u' tego grafu, mamy 3*		wierzchołków 'v' które spełniają

warunek |u ∩ v| = 1

	9 3		6 2
mnożąc to razy ilość wierzchołków otrzymamy 3*		*		, ale przez 2

bo liczyliśmy podwójnie

	9 3   6 2   3* *
graf ma więc		krawędzi
	2

poaw: Dzięki, taka ma być odpowiedź. A skąd się bierze 3 * 6 po 2? Mógłbyś to wyjaśnić?

Adamm: u = {a, b, c}, a, b, c∊{1, 2, ..., 9}, prawda |u ∩ v| oznacza że jeden z 'a', 'b', 'c' jest wspólnym punktem, a resztę musimy dobrać z innych '3', bo wybieramy jeden z 'a', 'b', 'c'

6 2
	, bo wybieramy dwa punkty z {1, 2, ..., 9}, różne od 'a', 'b', 'c'

Adamm: |u ∩ v| = 1

poaw: Rozumiem. A z krawędziami? To jest po prostu to samo tylko razy ilość wierzchołków i przez 2 bo sie powtarzają?

poaw: Dzięki wielkie!