Teoria grafów - zadania

[PoisonPrince]

Witam. Bardzo proszę o pomoc lub przynajmniej podpowiedź w rozwiązaniu poniższych dwóch zadań.

1. Pokaż, że jeżeli graf dwudzielny o dwupodziale \(\displaystyle{ \left( X,Y\right)}\) jest \(\displaystyle{ k}\)- regularny, \(\displaystyle{ k>0}\), to \(\displaystyle{ \left| X\right|=\left| Y\right|}\).

2. Niech \(\displaystyle{ G}\) będzie grafem prostym, 5-regularnym na 10 wierzchołkach. Niech \(\displaystyle{ S}\) będzie podzbiorem zbioru wierzchołków takim, że \(\displaystyle{ \left| S\right|=6}\) oraz liczba krawędzi podgrafu \(\displaystyle{ G\left[ S\right]}\) grafu \(\displaystyle{ G}\) indukowanego zbiorem wierzchołków \(\displaystyle{ S}\) jest równa 9. Ile jest krawędzi o jednym końcu w \(\displaystyle{ S}\) i drugim w \(\displaystyle{ V\left( G\right)-S}\)?

Z góry dziękuję za pomoc.