hi everyone. im a newbie here and i really need your help in answering the following problems in graph theory. hope somebody could help me. thanks to all.

1. Let G be a connected graph of order n. Prove that for every positive integer k ≤ n, G has a connected subgraph of order k.

2. Let G be a connected graph. Prove that any two longest paths in G must have at least one common vertex.

3. How many bridges does a tree of order n have?

4. Let T be a tournament of order n > 1. Prove that there is a vertexvЄ V(T) with the property that: For every vertex x Є V(T) with x ≠ v ,either (v,x) Є A(T) or (v,y), (y,x) Є A(T) for some y Є V(T).

5. Is the polynomial λ4 - 5λ3 +4λ2 chromatic? Prove your answer.

6. Prove that the graphs below are non-isomorphic but they have the same chromatic polynomial.