Let G = (V, E) be a graph. Define xi(G) = sum_d (i_d * d), where i_d is the number of vertices of degree d in G. If S an...

Question

Let G = (V, E) be a graph. Define xi(G) = sum_d (i_d * d), where i_d is the number of vertices of degree d in G. If S and T are two different trees with xi(S) = xi(T), then A. |S| = 2|T|  B. |S| = |T| - 1  C. |S| = |T|  D. |S| = |T| + 1

Accepted Answer

|S| = |T|  (Option C) The quantity xi(G) just adds up every vertex's degree: a vertex of degree d is counted d times, so xi(G) = sum of all degrees = 2|E| (Handshaking Lemma). A tree on |V| vertices always has exactly |V|-1 edges, so xi = 2(|V|-1). Equal xi therefore forces equal vertex counts.