91Ó°ÊÓ

What is the number of edges in a \(K^{n}\) ?

Let \(G\) be a graph containing a cycle \(C\), and assume that \(G\) contains a path of length at least \(k\) between two vertices of \(C\). Show that \(G\) contains a cycle of length at least \(\sqrt{k}\). Is this best possible?

\({ }^{+}\)Find a good lower bound for the order of a connected graph in terms of its diameter and minimum degree.

Show that the components of a graph partition its vertex set. (In other words, show that every vertex belongs to exactly one component.)

Show that every 2-connected graph contains a cycle.

Is there a function \(f: \mathbb{N} \rightarrow \mathbb{N}\) such that, for all \(k \in \mathbb{N}\), every graph of minimum degree at least \(f(k)\) is \(k\)-connected?

\({ }^{+}\)Let \(\alpha, \beta\) be two graph invariants with positive integer values. Formalize the two statements below, and show that each implies the other: (i) \(\alpha\) is bounded above by a function of \(\beta\); (ii) \(\beta\) can be forced up by making \(\alpha\) large enough. Show that the statement (iii) \(\beta\) is bounded below by a function of \(\alpha\) is not equivalent to (i) and (ii). Which small change will make it so?

Show that every tree \(T\) has at least \(\Delta(T)\) leaves.

Show that a tree without a vertex of degree 2 has more leaves than other vertices. Can you find a very short proof that does not use induction?

Show that every automorphism of a tree fixes a vertex or an edge.