public static Graph tree(int V) {
		Graph G = new Graph(V);

		// special case
		if (V == 1)
			return G;

		// Cayley's theorem: there are V^(V-2) labeled trees on V vertices
		// Prufer sequence: sequence of V-2 values between 0 and V-1
		// Prufer's proof of Cayley's theorem: Prufer sequences are in 1-1
		// with labeled trees on V vertices
		int[] prufer = new int[V - 2];
		for (int i = 0; i < V - 2; i++)
			prufer[i] = StdRandom.uniform(V);

		// degree of vertex v = 1 + number of times it appers in Prufer sequence
		int[] degree = new int[V];
		for (int v = 0; v < V; v++)
			degree[v] = 1;
		for (int i = 0; i < V - 2; i++)
			degree[prufer[i]]++;

		// pq contains all vertices of degree 1
		MinPQ<Integer> pq = new MinPQ<Integer>();
		for (int v = 0; v < V; v++)
			if (degree[v] == 1)
				pq.insert(v);

		// repeatedly delMin() degree 1 vertex that has the minimum index
		for (int i = 0; i < V - 2; i++) {
			int v = pq.delMin();
			G.addEdge(v, prufer[i]);
			degree[v]--;
			degree[prufer[i]]--;
			if (degree[prufer[i]] == 1)
				pq.insert(prufer[i]);
		}
		G.addEdge(pq.delMin(), pq.delMin());
		return G;
	}