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

Basic Graph Theory Problem Set II for RMO and INMO

  1. An Eulerian trail in a digraph is a trail containing all the edges. An Eulerian circuit is a closed trail containing all the edges. Show that a digraph X contains an Eulerian circuit if and only if d^{+}(v)=d^{-}(v) for every vertex v and the underlying graph has at most one component.
  2. Determine for what values of m \ge 1 and n \ge 1 is K_{m,n} Eulerian.
  3. What is the maximum number of edges in a connected, bipartite graph of order n?
  4. How many 4-cycles are in K_{m,n}?
  5. Let Q_{n} be the n-dimensional cube graph. Its vertices are all the n-tuples of 0 and 1 with two vertices being adjacent if they differ in precisely one position. Show that Q_{n} is connected and bipartite.

More later,

Nalin Pithwa

Basic Graph theory problem set I for RMO and INMO

  1. Is there a simple graph of 9 vertices with degree sequence 3, 3, 3, 3, 5, 6, 6, 6, 6?
  2. Is there a bipartite graph of 8 vertices with degrees 3, 3, 3, 5, 6, 6, 6, 6?
  3. In a simple graph with at least two vertices, show that there are at least two vertices with the same degree.
  4. directed graph (or digraph) is a graph X together with a function assigning to each edge, an ordered pair of vertices. The first vertex is called the tail of the edge and the second is called the head. To each vertex, v, we let d^{+}(v) be the number of the edges for which v is the tail and d^{-}(v) the number for which it is the head. We call d^{+}(v) the outdegree and d^{-}(v) the indegree of v. Prove that \sum_{v}d^{+}(v)=\sum_{v}d^{-}(v)= \#E(X) where the sum is over the vertex set of X.
  5. In any digraph, we define a walk as a sequence v_{0}, e_{1}, v_{1}, e_{2}, \ldots, e_{k}, v_{k} with v_{i-1} the tail of e_{i} and v_{i} its head. The analogous notions of trail, path, circuit, and cycle are easily extended to digraphs in the obvious way. If X is a digraph such that the outdegree of every vertex is at least one, show that X contains a cycle.

More later,

Nalin Pithwa