GATE CSE 2017 Set 2 | Question: 23

Question

$G$ is an undirected graph with $n$ vertices and $25$ edges such that each vertex of $G$ has degree at least $3$. Then the maximum possible value of $n$ is _________ .

Answer 1

Ans : 17

Sum of Degrees of Vertices Theorem

If G = (V, E) be a non-directed graph with vertices V = {V₁, V₂,…V_n} then

n∑i=1 deg(V_i) = 2|E|

If the answer is 16 i.e. 16 Vertices of which degree of each vertex is 3 then Sum of degree of all the vertices is 48 but according to Sum of degree of Vertices therom it should be 2*25= 50. Hence, the answer should be 17.

Comments

The number of odd degree vertices has to be even.

---

Minimum degree is 3 . so if you do 16*3 = 48 then remaining are two which cannot be covered by any vertex. So we do 15*3 = 45 and last vertex has degree 5. So maximum is 16