edited by
1,076 views
2 votes
2 votes

Consider an undirected graph with $n$ vertices, vertex $1$ has degree $1$,while each vertex $2,3,.............,n-1$ has degree $4$.The degree of vertex $n$ is unknown. Which of the following statement must be true?

  1.  Vertex $n$ has degree $1$
  2.  Graph is connected
  3. There is a path from vertex $1$ to vertex $n$
  4. Spanning tree will include edge connecting vertex $1$ and vertex $n$
edited by

3 Answers

0 votes
0 votes
I think answer should be D because spanning tree will include all vertices of graph .

 Option A is wrong because vertex N must have odd degree but not neccessarly 1 . since in a graph no. of odd degree vertices must be even and in given graph  all have even except 1 . thats why

option B it is not fixed that graph  must be connected it may be a is connected .

Option C if graph is disconnected then there is no path ib between 1 And N .

Correct me if i am wrong ;?
edited by

Related questions

2 votes
2 votes
1 answer
1
hem chandra joshi asked Oct 24, 2017
6,877 views
What does it means ?An undirected graph has an even number of vertices of odd degree. But let a 4 vertex cycle graph if it not complete having even vertex and even degree...
2 votes
2 votes
1 answer
3
Mk Utkarsh asked Jan 10, 2018
2,847 views
There is a simple graph with 65 edges containing vertices of degree 2,3 and 4. In which vertices with degree 3 are twice the number of vertices with degree 4 and there ar...
2 votes
2 votes
1 answer
4
srestha asked Jan 9, 2018
1,606 views
Consider the graph with 11 vertices and 16 edges. The maximum value of minimum degree of the graph is __________________