Let \(G=(V, E)\) be a graph. Define \(\xi(G) = \sum\limits_d i_d*d\) , where…
2010
Let \(G=(V, E)\) be a graph. Define \(\xi(G) = \sum\limits_d i_d*d\) , where id 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\)
Attempted by 162 students.
Show answer & explanation
Correct answer: C
Key idea: express xi(G) in terms of the number of vertices for a tree.
For any graph G, xi(G) = sum of degrees of all vertices = 2|E|.
For a tree with |V| vertices, |E| = |V| - 1, so xi = 2(|V| - 1).
If xi(S) = xi(T), then 2(|S| - 1) = 2(|T| - 1), which simplifies to |S| = |T|.
Therefore, the two trees must have the same number of vertices.