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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s