Skip to content
GATETECH
Official PYQ · 2010Q1Graphs: Connectivity, Matching, ColouringMCQ1 mark

GATE CS 2010 Q1 — Graphs: Connectivity, Matching, Colouring

Explain with AI

Let G=(V,E)G=(V, E) be a graph. Define ξ(G)=∑did∗d\xi(G) = \sum\limits_d i_d*d, where idi_d is the number of vertices of degree dd in G.G. If SS and TT are two different trees with ξ(S)=ξ(T)\xi(S) = \xi(T), then

Choose one option
View worked solution

Answer: C

By definition, ξ(G)=∑did⋅d\xi(G) = \sum_d i_d \cdot d is the sum of the degrees of all vertices in the graph GG.

According to the Handshaking Lemma, the sum of degrees of all vertices in any graph is equal to twice the number of edges, ∣E∣|E|:

ξ(G)=2∣E∣\xi(G) = 2|E|

For any tree TT with nn vertices, the number of edges is always ∣E∣=n−1|E| = n - 1. Therefore, for a tree:

ξ(T)=2(∣T∣−1)\xi(T) = 2(|T| - 1)

Given that SS and TT are two trees with ξ(S)=ξ(T)\xi(S) = \xi(T), we have:

2(∣S∣−1)=2(∣T∣−1)  ⟹  ∣S∣−1=∣T∣−1  ⟹  ∣S∣=∣T∣2(|S| - 1) = 2(|T| - 1) \implies |S| - 1 = |T| - 1 \implies |S| = |T|

Thus, the number of vertices in both trees must be equal.

Free practice · Your answers on this page are not saved.

Published
Report a correction
Keep exploringMore Graphs: Connectivity, Matching, Colouring questions