edited by
5,412 views
32 votes
32 votes

In an undirected graph $G$ with $n$ vertices, vertex $1$ has degree $1$, while each vertex $2,\ldots,n-1$ has degree $10$ and the degree of vertex $n$ is unknown, Which of the following statement must be TRUE on the graph $G$?

  1. There is a path from vertex $1$ to vertex $n$.
  2. There is a path from vertex $1$ to each vertex $2,\ldots,n-1$.
  3. Vertex $n$ has degree $1$.
  4. The diameter of the graph is at most $\frac{n}{10}$
  5. All of the above choices must be TRUE
edited by

3 Answers

Best answer
45 votes
45 votes

We have to recall couple of theorems before solving this question.

  1. Number of odd degree vertices in any connected component of a graph is even.
  2. The degree sum of all the vertices in any connected component of a graph is even.

Now in this question graph $G$ has $n-2$ vertices with degree $10,$ one vertex with degree $1.$
Because of theorem (1), vertex $n$ and vertex $1$ should be in the same connected component.

Proof: Lets suppose vertex $1$ and vertex $n$ are not in the same connected component. Also assume that vertex $1$ is in component $C_1.$ Now $C_1$ has only one vertex with odd degree which is vertex $1,$ because vertex $2$ to vertex $n-1$ has even degree (10) and this violates theorem (1). So, $C_1$ must have vertex $1$ as well as vertex $n$ and vertex $n$ should have odd degree.

Now, since vertex $1$ and vertex $n$ are in the same connected component and the given graph is undirected so, there must be a path from vertex $1$ to vertex $n.$ Hence option (a) is true.

Option (b) is false. Proof by counter example:
Lets take a graph $G$ where $n=13$ with two connected components $C_1$ and $C_2.$ $C_1$ has two vertices vertex $1$ and vertex $n$ and only one edge $(\text{vertex } 1,\text{vertex } n).$ Hence, degree of vertex $1$ as well as vertex $n$ is $1.$ $C_2$ has rest $11$ vertices (vertex $2$ to vertex $n-1)$ and $C_2$ is a complete component (there is exactly one edge between every pair of vertices of $C_2),$ hence degree of vertex $2,\ldots,$ vertex $n-1$ is $10.$ In this graph there is no path from vertex $1$ to vertex $2,\ldots,$ vertex $n-1.$.

Option (c) is False. Proof by counter example:

Lets take graph $G$ where  $n=12$ and each pair of vertices from vertex $2$ to vertex $n$ are connected with each other by an edge and additionally there is an ede between vertex $n$ and vertex $1.$ Hence, vertex $1$ has degree $1$ and  vertex $2,\ldots,$ vertex $n-1$ has degree $10$  and vertex $n$ has degree $11.$ In this graph vertex $n$ has degree $11,$ and hence option C is wrong.

Option (d) is false.
Proof: As we have seen an example as part of proving that option (b) is wrong where, graph $G$ can be disconnected and a disconnected graph has infinite diameter. Hence, option (d) is wrong.

Option (e) is false since options $b,c,d$ are false.

edited by
8 votes
8 votes

Only one statement is important to resolve this question 

Number of vertices of odd degree in a graph must be even 

so degree of vertex $1$ is $1$ and rest $2,...,n-1$ are even 

which concludes degree of vertex $n$ must be odd 

degree of  vertex $n$ can be 1,3,5,7...$

if degree of vertex $n$ is $1$ then statement b becomes false 

if degree of  vertex $n$ is $3,5,7 ...$ then statement c and d become false 

only statement hold is (a).

edited by
Answer:

Related questions

30 votes
30 votes
6 answers
1
5 votes
5 votes
1 answer
3