by 
Anonymous
ANSWERS: 1
-
If you can't do this, you should probably drop graph theory. Elementary graph theory contains only two difficult proofs: The planar graph theorem, and Euler's formula. This isn't either of those. 2-chromatic means you can assign one of 2 colors to each vertex so that no two vertices are directly connected that have the same color. A tree can be built recursively by adding a vertex joined with an edge to an existing vertex. Start with a tree with two connected vertices. Color them red and black. The only edge has different colors at each end. Now when you build an arbitrary tree, you add a vertex and an edge connected to an existing vertex. Just make sure the vertex you added has the opposite color to the vertex it was connected to. Every edge you add has a different color at each end, so all the vertices in the whole tree can be colored with the two colors, and no two vertices with the same color are directly connected.
RELATED QUESTIONS
Copyright 2023, Wired Ivy, LLC