5 votes 5 votes A simple graph is one in which there are no self loops and each pair of distinct vertices is connected by at most one edge. Let G be a simple graph on 8 vertices such that there is a vertex of degree 1, a vertex of degree 2, a vertex of degree 3, a vertex of degree 4, a vertex of degree 5, a vertex of degree 6 and a vertex of degree 7. Which of the following can be the degree of the last vertex? (A) 3 (B) 0 (C) 5 (D) 4 Graph Theory graph-theory discrete-mathematics + – Parshu gate asked Nov 13, 2017 Parshu gate 1.0k views answer comment Share Follow See all 7 Comments See all 7 7 Comments reply Show 4 previous comments Akash Mittal commented Nov 14, 2017 reply Follow Share why not 0? 0 votes 0 votes nikkey123 commented Nov 19, 2017 reply Follow Share becoz if we take 0 it will no more be a proper graphical sequence 0 votes 0 votes arun yadav commented Oct 13, 2020 reply Follow Share 0 IS NOT POSSIBLE BECAUSE MAX DEGREE IS 7.HENCE VERTEX WITH DEGREE 7 IS CONNECTED WITH ALL OTHER VERTICES.HENCE 0 DEGREE IS NOT POSSIBLE 0 votes 0 votes Please log in or register to add a comment.
2 votes 2 votes 1+2+3+4+5+6+7+x=even 28+x=even So x is even. So option a,c eliminated. Also, there is a vertex with degree 7. So x's degree cant be 0. So option d is a possible value. ayush.5 answered Oct 14, 2020 ayush.5 comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes ∑deg=2e total degree is 1+2+3+4+5+6+7+x it as given that "every pair of vertices are connected with at most one edge" which means graph is connected 28+x = 2e by looking at option we can say x=4 because ∑deg=even Hence , option (a) is correct. Akash Mittal answered Nov 19, 2017 Akash Mittal comment Share Follow See 1 comment See all 1 1 comment reply ayush.5 commented Oct 14, 2020 reply Follow Share atmost one edge also include zero edge. Having atmost one edge doesnt mean the graph will be connected. 0 votes 0 votes Please log in or register to add a comment.