3-2, 3-4, 3-7, 3-9, 4-1, 4-8, 4-9, 4-29

3-2

Choose a node in graph G as as starter to run BFS, if the graph is not connected, choose another after creating one BFS tree. It cost O(m+n) time, if the edge E in graph G is not in BFS tree, then the graph contains an edge.

如果第二次搜到这个点的时候说明存在环，一遍搜就可以，否则应该是一棵树。这个使用BFS 或者DFS都是可以的。如果给定了m,n,只要边的个数大于点的个数就可以判定了。

如果是显然（eg.bfs)的算法，也要说明是用了什么算法，如果是不这么显然的，需要加伪代码+文字描述

3-4

For each component C of G
	choose a starting node s randomly and label it A
//  BFS 
	Mark s as  'Visited',
	Initialize R=s
	Define layer L(0)=s
	for i=0,1,2..
		for each node u in L(i)
			Consider each edge (u, v) incident to v
			if (v is not marked 'Visited'){
			Mark v 'Visited',
			If ( judgment (u,v) was 'same')
				label v the same as u
			else
				// (the judgment was ''different',)
				label v the opposite of u
			Add V to the set R and to layer L(i+1)
		}
// check consistency
	for each edge (u, v)
		if (the judgment was same,)
			If u and v have different labels
				there is an inconsistency
		else 
		// (the judgment was "'different',)
			If u and v have same labels
				there is an inconsistency

after the checking phase, there exist no inconsistency , then it is consistent.

constructing G takes O（m+n)time, BFS takes O(m+n)time, check consistency takes O(m)time, so the total time is O(m+n) 。

3-7

If the G is not connect, then there must at lease 2 components in G. For any component C of G, because every node of G has degree at least n/2, so C has at least (n/2 +1) nodes. so there must at least 2*(n/2+1) nodes in G, which contradict with n nodes in G. Consequently, the graph is connected.

稠密图：每个点的度都> 1/2 n

假设不连通就分成两部，这样一定有一部分<1/2 n, 更强的结论， 这样的图存在Hamilton回路

反证法