Suppose G is a fixed but arbitrary graph. Prove or Disprove that the roots of p(G,x) are all real.
Prove: All roots of p(G,x) are all real.
Proof: Let us first recall the definition of Characteristic polynomial p(G,x).
The characteristic polynomial of G is defined as
where is adjacency matrix of G.
No matter what is the graph G, the adjacency matrix of G is always is a symmetric matrix. That means, p(G,x) is nothing but a characteristic polynomial of a symmetric matrix. Now we know that the root of characteristic polynomial of a symmetrix matrx (also known as eigenvalue) is always real. Hence all roots of p(G,x) are real.
Get Answers For Free
Most questions answered within 1 hours.