Zadania z matematyki dyskretnej do sprawdzenia

[gardner]

1.1. W każdym grafie liczba wierzchołków stopni nieparzystych jest parzysta.
\(\displaystyle{ \sum_{}^{} degv=2\left| E\right|}\)
\(\displaystyle{ \sum_{st.wierzcholkow parzystych}^{} + \sum_{st.wierzcholkow nieparzystych}^{} = parzysta}\)
Z tego wynika,że suma wierzchołków nieparzystych musi być parzysta.

1.2. Jeśli stopień każdego wierzchołka grafu G jest większy lub równy 2 to każdy wierzchołek
leży na pewnym cyklu prostym.

Tu nie bardzo wiedziałem jak się zabrać.

1.4. W każdym grafie G istnieje droga prosta długości co najmniej najmniejszego stopnia wierzchołka grafu.
Tu mam kontrprzykład :\(\displaystyle{ K_{3}}\)

1.5. Jeśli G jest samo dopełniający się to reszta z dzielenia przez \(\displaystyle{ 4}\) liczby wierzchołków wynosi \(\displaystyle{ 0}\) lub \(\displaystyle{ 1}\)
Liczba krawędzi grafu samo dopełniającego się jest połową krawędzi jaka występuje w grafie pełnym. Mamy więc,że \(\displaystyle{ \left| E\right|= \frac{n(n-1)}{4}}\) Z tego wynika,że musi przystawać modulo \(\displaystyle{ 4}\) do \(\displaystyle{ 0}\) lub \(\displaystyle{ 1}\).

1.6. Jeśli najmniejszy stopień wierzchołka w grafie \(\displaystyle{ G}\) wynosi co najmniej \(\displaystyle{ 2}\) to w \(\displaystyle{ G}\) istnieje cykl.
Tutaj chyba trzeba wziąć najdłuższą drogę w naszym grafie. Jeżeli rozpatrzymy pierwszy wierzchołek naszej drogi to musi on mieć więc 2 sąsiadów. Jeden z nich oczywiście należy do naszej drogi a drugi:
jeśli nie należy do drogi to znajdziemy drogę dłuższą ,więc sprzeczność. Jeśli nie,to musi należeć do drogi,więc powstaje nam cykl (oczywiste po narysowaniu rysunku)
1.7. Podać nieskończenie wiele grafów \(\displaystyle{ G}\) takich, że \(\displaystyle{ G}\) jest izomorficzny ze swoim dopełnieniem.
Tutaj nie miałem pomysłu jak ruszyć.
1.8. Scharakteryzować grafy \(\displaystyle{ G}\) takie, że każdy indukowany podgraf \(\displaystyle{ G}\) jest spójny.
Czy odpowiedzią są wszystkie grafy pełne?
1.10. W każdym k-regularnym grafie istnieje \(\displaystyle{ 1/2 k}\) rozłącznych krawędzi.
Tutaj nie wiedziałem jak przeprowadzić w miarę rozsądnie dowód. Proszę o wskazówki i sugestie.

[MatXXX]

Ad. 1.4: Chyba nie. Znajdziesz drogę długości 2 w trójkącie, czyż nie?

[bakala12]

1.2. Jeżeli przez cykl prosty rozumiesz cykl w którym wierzchołki się nie powtarzają to to nie jest prawda i łatwo podać kontrprzykład.

[gardner]

Mógłbyś go podać? Porysowałem trochę ale zawsze znajduję jakiś cykl prosty

[bakala12]

Oto przykład. Jak dla mnie "środkowy" wierzchołek nie leży na żadnym cyklu prostym
\(\displaystyle{ \begin{tikzpicture}
\draw (2,0)--(1,1)--(0,0)--(1,-1)--(2,0)--(3,0.5)--(4,0)--(5,1)--(6,0)--(5,-1)--(4,0)
\end{tikzpicture}}\)

[gardner]

Nie wiem dlaczego ale sprawdzałem tylko grafy regularne.Dzięki wielkie