Question

Suppose G is a fixed but arbitrary graph. Prove or Disprove that the roots of p(G,x)...

Suppose G is a fixed but arbitrary graph. Prove or Disprove that the roots of p(G,x) are all real.

Math   Advanced-Math   
0 0
Add a commentTranscribed image text
Next >

Homework Answers

Answer #1

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.

0 0
Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Log In

Sign Up

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
(a) Prove or disprove: if H and K are subgroups of G, then H ∩ K...
(a) Prove or disprove: if H and K are subgroups of G, then H ∩ K is a subgroup of G. (b) Prove or disprove: if H is an abelian subgroup of G, then G is abelian
) Prove or disprove the statements: (a) If x is a real number such that |x...
) Prove or disprove the statements: (a) If x is a real number such that |x + 2| + |x| ≤ 1, then |x ^2 + 2x − 1| ≤ 2. (b) If x is a real number such that |x + 2| + |x| ≤ 2, then |x^ 2 + 2x − 1| ≤ 2. (c) If x is a real number such that |x + 2| + |x| ≤ 3, then |x ^2 + 2x − 1 |...
Prove or disprove the following statements. Remember to disprove a statement you have to show that...
Prove or disprove the following statements. Remember to disprove a statement you have to show that the statement is false. Equivalently, you can prove that the negation of the statement is true. Clearly state it, if a statement is True or False. In your proof, you can use ”obvious facts” and simple theorems that we have proved previously in lecture. (a) For all real numbers x and y, “if x and y are irrational, then x+y is irrational”. (b) For...
Prove or disprove the following: (a) Every 3-regular planar graph has a 3-coloring. (b) If ?=(?,?)...
Prove or disprove the following: (a) Every 3-regular planar graph has a 3-coloring. (b) If ?=(?,?) is a 3-regular graph and there exists a perfect matching of ?, then there exists a set of edges A⊆E such that each component of G′=(V,A) is a cycle
Prove or disprove that [(p → q) ∧ (p → r)] and [p→ (q ∧ r)]...
Prove or disprove that [(p → q) ∧ (p → r)] and [p→ (q ∧ r)] are logically equivalent.
Graph Theory Prove that if G is a graph with x(G-v-w)=x(G)-2 for every pair of vertices...
Graph Theory Prove that if G is a graph with x(G-v-w)=x(G)-2 for every pair of vertices v and w in G, then G is complete. Hint: assume G is not complete.
(§2.1) Let a,b,p,n ∈Z with n > 1. (a) Prove or disprove: If ab ≡ 0...
(§2.1) Let a,b,p,n ∈Z with n > 1. (a) Prove or disprove: If ab ≡ 0 (mod n), then a ≡ 0 (mod n) or b ≡ 0 (mod n). (b) Prove or disprove: Suppose p is a positive prime. If ab ≡ 0 (mod p), then a ≡ 0 (mod p) or b ≡ 0 (mod p).
Prove or disprove that for any events A and B, P(A) + P(B) − 1 ≤...
Prove or disprove that for any events A and B, P(A) + P(B) − 1 ≤ P(A ∩ B) ≤ min{P(A), P(B)}.
Prove or disprove the claim that a directed connected graph is strongly connected if every node...
Prove or disprove the claim that a directed connected graph is strongly connected if every node in the graph has at least one incoming edge and at least one outgoing edge.
(a) Prove or disprove: Let H and K be two normal subgroups of a group G....
(a) Prove or disprove: Let H and K be two normal subgroups of a group G. Then the subgroup H ∩ K is normal in G. (b) Prove or disprove: D4 is normal in S4.
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT