GATE 2017 CS (CS2) – Question 33

Engineering Mathematics · Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) · 1 mark · Numerical answer

An undirected graph has n vertices, 25 edges and every vertex has degree at least three. Find the greatest possible n.

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: 16.0 to 16.0

Explanation

Handshaking gives $3n\le\sum d(v)=50$, so n≤16. This is attainable: start with a cubic graph on sixteen vertices (24 edges), then add a nonedge to reach 25 while retaining minimum degree three. Thus maximum n=16.

More Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) questions

GATE 2012 CS (CS1) Q27 – A connected simple planar graph has ten vertices and fifteen edges. How many bounded faces…
GATE 2012 CS (CS1) Q36 – Which graph A,B,C,D is isomorphic to the given graph?
GATE 2013 CS (CS1) Q35 – For undirected graphs, P: The number of odd-degree vertices is even. Q: The sum of all…
GATE 2013 CS (CS1) Q36 – The line graph L(G) has one vertex per edge of simple G, and joins vertices iff their G…
GATE 2011 CS (CS1) Q27 – The drawings show complete graph K₄ and cube graph Q₃. Which is true?
GATE 2010 CS (CS1) Q11 – For graph G=(V,E), let (G)= di dd, where i d counts vertices of degree d. If different…

All Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) questions →