# Basic Graph Theory Problem Set III for RMO and INMO

1. Show that $Q_{n}$ has $2^{n}$ vertices and $n.2^{n-1}$ edges.
2. How many 4-cycles are in $Q_{n}?$
3. Does $Q_{n}$ contain any copies of $K_{2,3}$?
4. Show that every graph X contains a bipartite subgraph with at least half the number of edges of X?
5. 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.
6. 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.
7. Show that in a connected graph any two paths of maximum length have at least one common vertex.
8. 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}$
9. 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.

More later,

Nalin Pithwa