## dan815 one year ago Graph Theory Induction proof Prove that if T is a tree, then the chromatic color of T is 2 or less, (Hint-use induction on P, the number of vertices of T) Defns- Tree is a graph with no cycles Chromatic color is the least number of colors the vertices can be colored so that no 2 adjacent vertices share the same color I dont understand what they mean by induction on P, what will the induction statement look like? side note they dont want you to use the theorem where every tree is a bipartite graph,

1. ganeshie8

Inducting on P means, you need to show that the statement is true for all $$P\in \mathbb{N}$$.

2. ganeshie8

1) Show that the statement is true for $$P=1$$ 2) Show that the statemetn is true for $$P=k+1$$ whenever the statement is true for $$P=k$$

3. dan815

hm

4. ganeshie8

why not simply take base case as $$P=1$$

5. dan815

that doesnt have diameter 3

6. ganeshie8

what diameter

7. dan815

oops ignore that im mixing up questions now

8. dan815

okay p=1

9. dan815

my mind is filled with currently solving another question, and now im taking a look at this, it somehow intertwined both questions into 1 lol

10. ganeshie8

Intuitively, atleast it is easy to see that you can paint all level1 vertices with color1, then level2 vertices with color2 then level3 vertices with color1 etc... since the graph is a tree, there wont be any cycles to join odd and even levels

11. ganeshie8

so any tree with P>1 is 2-chromatic

12. ganeshie8

|dw:1442977242648:dw|

13. dan815

i feel like this induction is not complete

14. ganeshie8

thats not induction, just showing it for convincing ourselves first

15. dan815

so i said X(T_1)<=1 To show if $X(T_P)<=2$, then $X(T_{p+1})$ any new vertex can be added so that its set to the color not equal to the vertex its joined to, i feel like this doesnt complete the proof that any T is less than or equal to 2 chromatic color, because we havent shown this to be true for all other non isomoprhic trees with p vertices

16. ganeshie8

For an induction proof : base case : for $$P=1$$, just color the vertex with color1, so the statement checks out Induction hypothesis : assume we can color a tree with vertices $$P=k$$ Induction step : Consider a tree with vertices $$P=k+1$$ and remove any one vertex; the rest of the graph is still a tree; which is $$2$$ chromatic from induction hypothesis. Simply connect back the removed vertex and color it with color different from its adjacent vertex. $$\blacksquare$$

17. dan815

nvm i guess its fine ill just state that the statement if X(T_p) <=2 for all non-isomorphic trees of T_p

18. ganeshie8

Keep in mind, particularly here, the induction fails miserably if you start with P=k and add a vertex. You must always start the induction step with P=k+1.

19. dan815

okay i see what u mean

20. dan815

so i just gotta say that we remove a vertex and we are in T_n case then we re add vertex with new color not equal to adj vertex

21. ganeshie8

Yes, but it doesn't work exactly... we still need to tweak a bit.. let me give u an example where it fails

22. ganeshie8

|dw:1442978241263:dw|

23. ganeshie8

suppose you remove the vertex $$A$$, then color the rest of tree what color does the vertex $$A$$ gets when you stitch it back ?

24. dan815

oh i see if we remove A then we cant use that argument

25. ganeshie8

yeah there should be a better way to approach this... this removing and adding thingy may not work

26. dan815

i can do 2 cases

27. dan815

either you have a vertex connected to multiple vertices or you have a vertex connected to just 1 vertex

28. ganeshie8

i think it might get messy..

29. dan815

ya theres gotta be a better way

30. dan815

theres no way ill be able to argue that the vertex i removed has to be connected to all all of vertices of the same color just because its a Tn graph now

31. dan815

oh wait i can!

32. dan815

nvm i cant

33. ganeshie8

|dw:1442978612649:dw|

34. ganeshie8

There is no way to connect back the A w/o using a third color so the previous idea is not going to work

35. dan815

okay i have an idea

36. dan815

say A is connected to multiple like u did there

37. dan815

then after connecting A its either connected to all diferernt colors or not, if it is conneted all diferent colors you are done, not suppose it is connected to the same color, then you remove that, once u remove it you have a Tn graph and u know there is some way to distribute colors so that X(Tn) <= then you place that point back in so that it is not equal the points that you removed it from atleast, if this new point has another connection that is equal, then remove that, you can continue this process until the point you remove in the end is an end point in the path

38. dan815

that doesnt really work but im wondering if we can build off that like is there a way to show that u can remove vertices such that u end up at the end of a path eventually

39. dan815

u must be able to right!!

40. dan815

this is my idea in a diagram

41. dan815

|dw:1442979234709:dw|

42. dan815

once you put A back in you will make sure it might be equal to some other color of another vertex, now u remove that vertex

43. dan815

|dw:1442979350004:dw|

44. dan815

then when you put it back in you will remove a vertex of the same color that is not A or B |dw:1442979373481:dw|

45. dan815

in this way since there are no cycles you must remove a point from the end where it only has 1 degree

46. dan815

and that case is very easy to prove

47. dan815

since you will never remove a point thhat you preoviously removed from this tn+1 graph in this process you must end up at an end point

48. dan815

would this work?

49. ganeshie8

that looks rather complicated but the construction definitely works!

50. dan815

ya that looks like a lot to write in this one proof lol

51. ganeshie8

i have a better idea

52. dan815

okay go on

53. ganeshie8

it is simple

54. ganeshie8

lets just make a choice of which vertex we remove

55. dan815

oh omg lol xD

56. dan815

ya okay that is done

57. ganeshie8

simply remove a "leaf vertex", the problem is solved :)

58. dan815

yep

59. ganeshie8

how do you know a leaf vertex always exists ?

60. dan815

well i can just say this, there is an end point to every tree once i remove the end point pof a tn+1 graph we have tn graph, and a tn graph can be chromatic 2 then when i connect my end point back in i will make sure its not equal to its adj point thus mainintg chromatic 2

61. ganeshie8

looks neat !

62. dan815

thanks a lot for your help