QUESTION 1

A _________ is the one in which every two pairs of vertices are connected.

	A.	complete graph
	B.	weighted graph
	C.	directed graph
	D.	none of the above.

10 points

QUESTION 2

If locality is a concern, you can use _______ to traverse the graph.

	A.	Breadth First Search (BFS)
	B.	Depth First Search (DFS)
	C.	Either BFS or DFS
	D.	None of the above.

10 points

QUESTION 3

The degree sequence of a simple graph is the sequence of the degrees of the nodes in the graph in decreasing order. Which of the following sequences can NOT be the degree sequence of any graph?

I. 7, 6, 5, 4, 4, 3, 2, 1

II. 6, 6, 6, 6, 3, 3, 2, 2

III. 7, 6, 6, 4, 4, 3, 2, 2

IV. 8, 7, 7, 6, 4, 2, 1, 1

	A.	I and II
	B.	III and IV
	C.	IV only
	D.	II and IV
	E.	None of the above.

10 points

QUESTION 4

Considering unit weight on all the edges, which walk gives the shortest path:

	A.	Breadth First Search (BFS)
	B.	Depth First Search (DFS)
	C.	Either BFS or DFS
	D.	None of the above.

10 points

QUESTION 5

Given an undirected graph G with V vertices and E edges, the sum of the degrees of all vertices is:

	A.	E
	B.	2E
	C.	V
	D.	2V
	E.	None of the above.