Question

Show that a graph problem using the number of vertices as the measure of the size of an instance is polynomially equivalent to one using the number of edges as the measure of the size of an instance.

Short answer

The number of edges in a graph, which can be expressed in terms of the vertices as \(\frac{n * (n-1)}{2}\), is polynomially related to the number of vertices (i.e., \(e = O(n^2)\) and \(n = O(\sqrt{e})\)). Therefore, the problem sizes measured in terms of vertices and edges are polynomially equivalent.

Step-by-step solution

Understand the maximum number of edges in a graph in relation to vertices

A simple undirected graph with 'n' vertices can have at most \(\frac{n * (n-1)}{2}\) edges (This is because every vertex can connect to at most 'n-1' other vertices and since the graph is undirected, we divide by 2). This relationship is a polynomial one.

Relating number of vertices and edges

Since the number of edges 'e' in a undirected graph can be expressed in terms of the vertices as \(\frac{n * (n-1)}{2}\), then 'n' (number of vertices) is polynomially related to 'e' (number of edges). Therefore, \(e = O(n^2)\) and \(n = O(\sqrt{e})\).

Polynomial equivalence

By the transitive nature of O notation, if one problem can be solved in polynomial time in terms of one measure (say vertices), then by substituting this measure with the other measure (edges) which we've shown to be polynomially related, then the problem can be solved in polynomial time in terms of this other measure as well. This indicates that problems using the number of vertices to measure its instance size are polynomially equivalent to problems using the number of edges to measure its instance size and vice versa.