Basic Graph Theory Problem Set III for RMO and INMO

Show that $Q_{n}$ has $2^{n}$ vertices and $n.2^{n-1}$ edges.
How many 4-cycles are in $Q_{n}?$
Does $Q_{n}$ contain any copies of $K_{2,3}$ ?
Show that every graph X contains a bipartite subgraph with at least half the number of edges of X?
Let X be a graph in which every vertex has even degree. Show that it is possible to orient the edges of X such that the indegree equals the outdegree for each vertex.
Show that a graph X is connected if and only if for any partition of its vertex set into two non-empty sets, there exists at least one edge between the two sets.
Show that in a connected graph any two paths of maximum length have at least one common vertex.
Let X be a graph with n vertices and e edges. Show that there exists at least one edge uv such that $d(u)+d(v) \ge \frac{4e}{n}$
If X is a graph on n vertices containing no $K_{3}$ ‘s then the number of edges of X is less than or equal to $\lfloor \frac{n^{2}}{4} \rfloor$ edges. Give an example of a graph on n vertices containing no $K_{3}$ ‘s with $\lfloor \frac{n^{2}}{4} \rfloor$ edges.