Hi everyone, this is my first post, and i need help(as soon as possible) with 2 exercises.
1.In a finite, simple graph G, let x != y be two vertices for which any path between x and y contains an even number of edges. Combine x and y into a single vertex {xy} which we connect with those vertices of G that at least one of x and y is connected with. Prove that this new graph has the same chromatic number as G.
2.Let a1<a2<...<ak be distinct positive integers. Proove that there exist a graph on exactly ak + 1 vertices such that the set of the degrees of the vertices are {a1,a2,...,ak}.
Thanks for any help!
dr.joarc