The GATE Grind

GATE 2010 CS (CS1) – Question 11

Engineering Mathematics · Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) · 1 mark · Multiple choice

For graph G=(V,E), let $\xi(G)=\sum_di_dd$, where i_d counts vertices of degree d. If different trees S,T satisfy ξ(S)=ξ(T), what follows?

  1. |S|=2|T|
  2. |S|=|T|−1
  3. |S|=|T|
  4. |S|=|T|+1

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (C) |S|=|T|

Explanation

The quantity ξ is the degree sum, equal to twice the edge count. A tree with v vertices has v−1 edges, so ξ=2(v−1). Equal ξ therefore forces equal vertex counts, |S|=|T|, C, although the trees may have different shapes.

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

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