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


Leave a Reply

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

You are commenting using your 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