# 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

This site uses Akismet to reduce spam. Learn how your comment data is processed.