upsc mathematics optional paper

Since every tree with 2 or more vertices is 2-chromatic. We see that a tree with even no. of vertices will have perfect matching as all vertices with the same color can be grouped together and a matching can be established between the two groups. If the tree has odd number of vertices,then no perfect matching can be established for obvious reason.    [proved ]

Since a tree is connected and has no cycle if one starts coloring any one vertex with a specific color and keeps on coloring every alternate vertex with another color, the entire graph can be colored with only two colors and since there is one and only one path between any two vertices in a tree, no two vertices will have the same color. Hence every Tree with 2 or more vertices is 2-Chromatic.    [Proved]                                                                 FIG (I)                                                                  FIG (II)

Let G be a Bi-partite graph.            So, V(G)=V1 U V2    Color every vertex in V1 by one color and every vertex in V2 by another Colour.    Then, clearly, this coloring is proper. Thus only two colors suffice to color G. so, G is 2 chromatic.    [Proved] image source :Google