graph = { 1 => [2, 3, 4], 2 => [1, 5, 6], 3 => [1], 4 => [1], 5 => [2], 6 => [2] }

nodes = graph.keys
arcweight = Hash.new(0)

nodes.each { |n1|
	order = Hash.new(0)
	todo = [n1]
	order[n1] = 1
	parent = { n1 => n1 }
	while n = todo.shift
		graph[n].each { |n2|
			if not parent[n2]
				order[n2] = order[n]+1
				parent[n2] = n
				todo << n2
				arcweight[[n, n2].sort] += 1
			end
		}
	end
}

p arcweight.sort_by { |k, v| v }