5.6 Exercises

1.

If $\delta(G)\geq 2$ , every graph has a cycle of length at least $\delta(G)+1$ .
2.

Prove that a graph $G$ with $g(G)=4$ and $\delta(G)\geq k$ has at least $2k$ vertices. Is $2k$ the best lower bound ?
3.

Prove that a $k$ -regular bipartite graph has no cut-edge for $k\geq 2$ .
4.

Suppose $G$ is a graph with at least one edge. Then there exists a subgraph $H$ such that $\delta(H)>\epsilon(H)\geq\epsilon(G)$ where recall that $\epsilon(G)$ was defined as the edge density of the graph (see Definition 2.21).
5.

If a graph $G=(V,E)$ on $n$ vertices has no $(k+1)$ -clique $k\geq 2$ then show that $|E|\leq(1-\frac{1}{k})\frac{n^{2}}{2}$ .

1.

Show that Dilworth’s theorem implies Erdös-Szekeres lemma.
2.

Let $n^{2}+1$ points be given in $\mathbb{R}^{2}$ . Prove that there is a sequence of $n+1$ points $(x_{1},y_{1})\ldots(x_{n+1},y_{n+1})$ for which either $x_{1}\leq x_{2}\leq\ldots x_{n+1}$ and $y_{1}\geq y_{2}\geq\ldots y_{n+1}$ holds or $x_{1}\leq x_{2}\leq\ldots x_{n+1}$ and $y_{1}\leq y_{2}\leq\ldots y_{n+1}$ holds.
3.

Show that the bound in the Erdös-Szekeres lemma is the best possible.
4.

Let $G$ be a graph with $g(G)=5$ and $\delta(G)\geq k$ . Show that $G$ has at least $k^{2}+1$ vertices.
5.

Show that Petersen graph (defined in Section 2.1) is the largest 3-regular graph with diameter 2.
6.

Let $G$ be a simple graph on $n$ vertices ( $n>3$ ) with no vertex of degree $n-1$ . Suppose that for any two vertices of $G$ , there is a unique vertex joined to both of them. If $x$ and $y$ are not adjacent show that $d(x)=d(y)$ . Now, show that $G$ is a regular graph.
7.

Show that a simple graph on $n$ vertices with $\lfloor n^{2}/4\rfloor$ edges and no triangles, then it is the complete bipartite graph $K_{k,k}$ if $n=2k$ or $K_{k,k+1}$ if $n=2k+1$ .
8.

If a simple graph on $n$ vertices has $e$ edges, then it has at least $\frac{e}{3n}(4e-n^{2})$ triangles.