function A = generate_connected(n)

	A = zeros(n,n);
	
	for k=1:n*n
		
		i = random_index(n);
		j = random_index(n);
	
		if i ~= j
			A(i,j) = 1;
			A(j,i) = 1;
		end
		
		if sum(sum(A^n==0)) == 0
			break
		end
	end

	extra = n / 4;
	
	for k=1:extra
		
		i = random_index(n);
		j = random_index(n);
	
		if i ~= j
			A(i,j) = 1;
			A(j,i) = 1;
		end
		
	end
	
	
function i = random_index(n)
	i = floor(rand * n) + 1;