Podaj stopień minimalny oraz liczbę krawędzi w grafie

[rivit]

\(\displaystyle{ X = \left\{ 1,2,3 ..., 9\right\} \\ G = \left( V, E\right)}\)

\(\displaystyle{ V}\) - zbiór wszystkich 3-elem. pozdbiorów zbioru X (wyliczyłem, że jest ich 84. \(\displaystyle{ \binom{9}{3}}\))
\(\displaystyle{ E}\) - zbiór krawędzi takich, że \(\displaystyle{ u,v \in E \Leftrightarrow \left| u \cap v\right| = 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.

[arek1357]

Zauważ, jedno, że jak weźmiesz np. punkt:

\(\displaystyle{ \left\{ 1,2,3\right\}}\)

to on ma krawędzie wspólne z następującymi punktami:

\(\displaystyle{ \left\{ 1,4,5\right\}}\)

\(\displaystyle{ \left\{ 1,6,7\right\}}\)

\(\displaystyle{ \left\{ 1,8,9\right\}}\)

\(\displaystyle{ \left\{ 2,4,5\right\}}\)

\(\displaystyle{ \left\{ 2,6,7\right\}}\)

\(\displaystyle{ \left\{ 2,8,9\right\}}\)

\(\displaystyle{ \left\{ 3,4,5\right\}}\)

\(\displaystyle{ \left\{ 3,6,7\right\}}\)

\(\displaystyle{ \left\{ 3,8,9\right\}}\)

Widać, że stopień takiego wierzchołka wynosi.: \(\displaystyle{ 9}\),

takich wierzchołków jak wyliczyłeś jest: \(\displaystyle{ 84}\)

\(\displaystyle{ \sum_{v \in V}^{}deg(v_{i})=2|E|}\)

ale jak widać:

\(\displaystyle{ \sum_{v \in V}^{}deg(v_{i})=84 \cdot 9=756}\)

czyli:

\(\displaystyle{ |E|=756:2=378}\)