Неравенство с броя на върховете и ребрата на неориентиран гр

[Гост]

Нека $G=(V,E)$ е неориентиран краен граф с $|V|=m$ върха и $|E|=n$ ребра.
Да се докаже, че $2n \leq m^2 - m.$

Да се докаже още, че ако $|V| \ge 3$ и съществува единствен връх от степен едно, то в графа има цъкъл.

[Петър Евгениев]

Нека $G=(V,E)$ е неориентиран краен граф с $|V|=m$ върха и $|E|=n$ ребра.
Да се докаже, че $2n \leq m^2 - m.$

Да се докаже още, че ако $|V| \ge 3$ и съществува единствен връх от степен едно, то в графа има цъкъл.

Понеже графът $G$ е неориентиран, то формулата на Ойлер влече , че
$$\sum_{v \in V} d_{G}(v) = 2|E|. $$
T.e. неравенството става $$2|E|= \sum_{v \in V}d_{G}(v) \leq |V|^2 - |V|,$$
което вече е много лесно да докажеш, защото всеки връх най-много ще да е от степен $|V|-1.$ Тоест оценяваме в горното $$\forall v \in V \left( d_{G}(v) \leq |V|-1 \right).$$
Това пък, на свой ред, дава оценката
$$2|E|= \sum_{v \in V}d_{G}(v) \leq \sum_{v \in V}(|V|-1) = |V|(|V|-1).$$
Неравенството е доказано.

[Петър Евгениев]

Нека $G=(V,E)$ е неориентиран краен граф с $|V|=m$ върха и $|E|=n$ ребра.
Да се докаже, че $2n \leq m^2 - m.$

Да се докаже още, че ако $|V| \ge 3$ и съществува единствен връх от степен едно, то в графа има цъкъл.

Дурого можем пак д го оценим , ама отдолу този път. Някаква ,ей такава, сметка
$$\exists ! v_0 \in V (d_{G}(v_0) = 1)\Longrightarrow \forall v \in V \setminus \{v_0 \}(d_{G}(v) \ge 2).$$
И сега
$$2|E| = 1 + \sum_{\substack{v \in V \\ v \ne v_0}}d_{G}(v) \ge 1+ (|V|-1)\cdot 2 =2|V|-1.$$
Та получаваме $|E| \ge |V| - \frac{1}{2}.$ Ама това в естевените числа си е $|E| \ge |V|.$ Това ми се струва достатъчно(а и необходимо), в неориентиран граф да има цикъл.