a) Egy gráfban $2n$ darab pont van, és minden pont foka legalább $n$. Legalább hány elemű egy lefogó élhalmaz a gráfban?
b) Egy 1001 pontú $G$ egyszerű gráfban $\tau{(G)}=1000$. Bizonyítsuk be, hogy $G$ teljes gráf.
a) Bizonyítsuk be, hogy minden $G$ egyszerű gráfra:
\( \chi{(G)} \cdot \alpha{(G)} \geq n \)
b) Bizonyítsuk be, hogy minden $G$ egyszerű gráfra:
\( 2\nu{(G)} \geq \tau{(G)} \)
c) Vajon minden $G$ egyszerű gráfban teljesül-e, hogy
\( \mid E(G) \mid \leq \Delta(G) \cdot \tau{(G)} \)
d) Bizonyítsuk be, hogy minden $G$ egyszerű gráfra:
\( \alpha{(G)} \left( \Delta(G)+1 \right) \geq n \)
e) Bizonyítsuk be, hogy bármely $G$ egyszerű gráfban:
\( \chi{(G)} + \alpha{(G)} \leq n +1 \)
f) Bizonyítsuk be, hogy bármely $G$ egyszerű gráfban:
\( \begin{pmatrix} \chi{(G)} \\ 2 \end{pmatrix} \leq \mid E(G) \mid \)
Határozzuk meg a Petersen-gráf gráfparamétereit.
A $G$ gráf csúcshalmaza $V(G)=\{1,2, \dots, 30 \}$. Az $x,y \in V(G)$ csúcsok akkor legyenek szomszédosak $G$-ben, ha $x \neq y$ és $x \cdot y$ osztható 6-tal. Határozzuk meg $\nu(G)$ értékét!
Egy $G$ gráf csúcsai legyenek a 100-nál nem nagyobb pozitív egészek. Két különböző csúcs pontosan akkor szomszédos $G$-ben, ha a megfelelő egészek relatív prímek. Határozzuk meg a gráfparamétereket!
Egy $G$ gráf csúcsai legyenek a 100-nál nem nagyobb pozitív egészek. Két különböző csúcs pontosan akkor szomszédos $G$-ben, ha a hozzájuk tartozó számok szorzata osztható 4-gyel. Határozzuk meg $\alpha{(G)}$ és $\rho{(G)}$ értékeit!
Egy 1000 csúcsú gráfban $\tau{(G)}=400$. Igazoljuk, hogy $G$-ben nincs teljes párosítás.
