Given an undirected graph G G G G , the problem is to determine whether or not

Given an undirected graph $G$, the problem is to determine whether or not $G$ is connected. Use an adversary argument to prove that it is necessary to look at all $(n^2-n)/2$ potential edges in the worst case.

Graph G:

A graph $G=(V,E)$ consists of a set of vertices $V$ and a set of edges $E$, such that each edge in $E$ is a connection between a pair of vertices in $V.{}^1$ The number of vertices is written $|V|$, and the number of edges is written $|E|.|E|$ can range from zero to a maximum of $|V{|}^2-|V|$. A graph with relatively few edges is called sparse, while a graph with many edges is called dense. A graph containing all possible edges is said to be complete.

 A graph whose edges are not directed is called an undirected graph (as illustrated by Figure 11.1(a)).

Figure 11.1 (a):