# Graph minors

A graph $H$ is a minor of a graph $G$ if $H$ is isomorphic to a graph obtained by contracting edges, removing edges and/or removing isolated vertices from $G$. For example the graph with two vertices and one edge is a minor of any graph with at least one edge.

Problem: Fix a graph $H$. Find a polynomial time algorithm that decides if a given graph $G$ has $H$ as one of its minors. The algorithm must be polynomial in the number of vertices of $G$.

Notice that such an algorithm proves that planarity of a graph can be decided in polynomial time.

# Simple and hard problems I

Given that an integer $p$ is prime, can you convince me in a reasonable amount of time of that fact? Stated otherwise: Is there a “short” formal argument that proves the fact that a given prime is indeed prime? Here “short” means that the argument can be written in $O(P(\mathrm{log} \,n))$ pages, for some polynomial $P$ independent of $n$.

Notice that there is always a short proof of the fact that a given composite number is composite, namely a non-trivial factorization.

Formally this last statement means that the problem of the deciding if a given integer is composite is in NP.

The excercise is to prove that the problem of deciding if a given integer is prime is in NP.

Remarks: The formal argument mentioned in the explanation is usually called certificate. Notice that the size of the certificate must be polynomial in the logarithm of $n$ because $n$ is representable by $\mathrm{log}\, n$ bits and thus the size of the input is $\mathrm{log}\, n$ and not $n$.