I'm currently working on some assignments, but I'm not getting anywhere. Maybe you can give me some ideas.
1) Show for a graph $G:=(V,E)$ with $n$ vertices and minimum graph degree $$ \delta = \left\lfloor \frac{(r-2)n}{r-1} \right\rfloor + 1 $$ contains a subgraph $K_r$.
I don't have any clue.
2) Show for a graph $G:=(V,E)$ with $n = |V(G)|\ge 5$ without triangles and who is not bipartite the following holds: $$ |E(G)| \le \left\lfloor \frac{(n-1)^2}{4} \right\rfloor + 1 $$
Here I think that a vertex $v$ with degree $d(v)=1$ should exist. Then $G':=G-v$ is a graph with $|V(G')| = n-1$ vertices and without triangles. According to Turan the graph $G'$ has maximal $$ |E(G')| \le \left\lfloor \frac{|V(G')|^2}{4} \right\rfloor $$ edges. And therefore $G$, due to the additional edge, has maximal the amount of edges as stated in the claim.
However, I cannot cleanly prove why such a vertex $v$ have to exist.
3) $G=(V,E)$ is a graph with $n = |V(G)| \ge 2$ without a hamiltonian path. Show that: $$ |E(G)| \le \binom{n}{2} - (n-1) $$ Determine the extremal graph and show the uniqueness.
I have no ideas here either. :( I would be grateful for any help!
Thank you very much
3)) Suppose to the contrary that $G$ has at least ${n\choose 2}−(n−1)+1$ edges. If $n=2$ then $G$ has an edge and so a Hamiltonian path. So let’s assume $n\ge 3$. We can try to show that $G$ has a Hamiltonian path directly, but a teaching way is to apply Ore's theorem. If $G$ is complete then it is Hamiltonian. Otherwise we add to it an arbitrary edge $e$ and obtain a graph $G’$ with at least ${n\choose 2}−n+3$ edges. Let $v$ and $w$ be any pair of distinct non-adjacent vertices of $G’$. Since in a complete graph on $n$ vertices each vertex has a degree $n-1$ and $G’$ lacks at most $n-3$ edges to a complete graph, $\deg v + \deg w\ge n-1+n-1-(n-3)-1=n$ (the last $-1$ is taken into account for an edge $vw$ is a complete graph). By Ore’s theorem $G’$ has a Hamiltonian cycle, so $G$, which is a $G’$ with a removed edge, has a Hamiltonian path.
Now suppose that $G$ is an extremal graph, that is a graph with ${n\choose 2}−(n-1)$ edges and without a Hamiltonian path. An instance of such graph is a complete graph with all edges incident to a fixed vertex removed. We claim that there are no other extremal graphs. Indeed, suppose to the contrary that $G$ is such a graph. If $G$ has at least three vertices of degree one then $n\ge 4$ and $G$ has at most ${n-3\choose 2}+3$ edges and, which follows ${n-3\choose 2}+3\ge {n\choose 2}−(n-1)$, and $n\le 2$, a contradiction.
Thus we can add an edge to $G$ such that the graph $G’$ has no vertices of degree one. An analysis of the Hamiltonicity proof of $G’$ shows that it can fail only if there exist two non-adjacent vertices $v$ and $w$ of $G’$ such that each edge which $G’$ lacks to a complete graph is incident either to $v$ or to $w$ and, moreover, $\deg v=\deg w=2$, $n>4$, and $v$ and $w$ have the same sets of neighbors. Thus $G’$ lacks $2(n-3)-1$ edges to a complete graph. Thus $2(n-3)-1\le n-2$, which follows $n\le 5$, so $n=5$ and $G’$ is isomorphic to a graph $K_5$ without a triangle. But then it is easy to check that the graph $G$, which is a graph $G’$ with one edge removed has a Hamiltonian path, a contradiction.