The following statement is true: If G = (V, E) is a graph, |V | = n, and |E| < n
ID: 3199593 • Letter: T
Question
The following statement is true: If G = (V, E) is a graph, |V | = n, and |E| < n?1, then G is not connected. The following “proof” is wrong. What is wrong with it?
A graph G = (V, E) is connected if for every pair of vertices u, v ? V , u is connected to v. Suppose G = (V, E) is a graph, |V | = n, and |E| < n ? 1. Consider any vertex v ? V (G). Since there are fewer than n ? 1 edges in G, the degree of v is less than n ? 1. So v has fewer than n?1 neighbors. Noting that |V ?{v}| = n?1, we find that there is at least one vertex of V ?{v} which is not connected to v. So G is not connected.
Explanation / Answer
The mistake is |V(v)| can't be exactly n-1.
?Since number of edges are less than n-1. So, deg of v can be n-2, n-3 and so on.....
?Make cases out of them
?1. If deg v = n-2 then we get two vertices which are not connected with v. hence G is disconnected
?2. If deg v= n-3 then we get three vertices which are not connected with v. hence G is disconnected
?and so on , the last case is
?deg v =1 i.e. v is isolated so not connected with any of the vertex. hence G is disconnected
similarly considering all the cases we can say that G is disconnected.
Or you can think like this also:
?As the graph has n vertices and no. of edges are less than n-1.
?So, while we try to go from one vertex to another we need n-1 edges which are not present here. so G is disconnected.