**Thanks to Simon Foundation : a youtube video.**

# graph theory for RMO and INMO

# Basic Graph Theory Problem Set III for RMO and INMO

- Show that has vertices and edges.
- How many 4-cycles are in
- Does contain any copies of ?
- Show that every graph X contains a bipartite subgraph with at least half the number of edges of X?
- 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.
- 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.
- Show that in a connected graph any two paths of maximum length have at least one common vertex.
- Let X be a graph with n vertices and e edges. Show that there exists at least one edge uv such that
- If X is a graph on n vertices containing no ‘s then the number of edges of X is less than or equal to edges. Give an example of a graph on n vertices containing no ‘s with edges.

More later,

Nalin Pithwa

# Basic Graph Theory Problem Set II for RMO and INMO

- 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 for every vertex v and the underlying graph has at most one component. - Determine for what values of and is Eulerian.
- What is the maximum number of edges in a connected, bipartite graph of order n?
- How many 4-cycles are in ?
- Let 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 is connected and bipartite.

More later,

Nalin Pithwa

# Basic Graph theory problem set I for RMO and INMO

- Is there a simple graph of 9 vertices with degree sequence 3, 3, 3, 3, 5, 6, 6, 6, 6?
- Is there a bipartite graph of 8 vertices with degrees 3, 3, 3, 5, 6, 6, 6, 6?
- In a simple graph with at least two vertices, show that there are at least two vertices with the same degree.
- A
**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 be the number of the edges for which v is the tail and the number for which it is the head. We call the**outdegree**and the**indegree**of v. Prove that where the sum is over the vertex set of X. - In any digraph, we define a
**walk**as a sequence with the tail of and 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