Determine all graphs $G$ with the following two properties: $\bullet$ G contains at least one Hamilton path. $\bullet$ For any pair of vertices, $u, v \in G$, if there is a Hamilton path from $u$ to $v$ then the edge $uv$ is in the graph $G$

For any natural $n$, $f(n)$ is the number of labeled digraphs with $n$ vertices such that for any vertex the number if in-edges is equal to the number of out-edges and the total of (in+out) edges is even. Let $g(n)$ be the odd-analogous of $f(n)$. Find $g(n)-f(n)$ with proof . [hide=original formulation] Dado $n$ natural, seja $f(n)$ o número de grafos rotulados direcionados com $n$ vértices de modo que em cada vértice o número de arestas que chegam é igual ao número de arestas que saem e o número de arestas total do grafo é par . Defina $g(n)$ analogamente trocando "par" por "ímpar" na definição acima. Calcule $f(n) - g (n)$. (Observação: Um grafo rotulado direcionado é um par $G = (V, E)$ onde $V = \{1, 2, …, n\}$ e $E$ é um subconjunto de $V^2 -\{(i, i); 0 < i < n + 1\}$).[/hide]

The edges of a graph $G$ are coloured in two colours. Such that for each colour all the connected components of this graph formed by edges of this colour contains at most $n>1$ vertices. Prove there exists a proper colouring for the vertices of this graph with $n$ colours.

Let $n$ and $k$ be positive integers. A simple graph $G$ does not contain any cycle whose length be an odd number greater than $1$ and less than $ 2k + 1$. If $G$ has at most $n + \frac{(k-1) (n-1) (n+2)}{2}$ vertices, prove that the vertices of $G$ can be painted with $n$ colors in such a way that any edge of $G$ has its ends of different colors.