A community for students.

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

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,

  • This Question is Closed
  1. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  2. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    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
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    hm

  4. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    why not simply take base case as \(P=1\)

  5. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    that doesnt have diameter 3

  6. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    what diameter

  7. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    oops ignore that im mixing up questions now

  8. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    okay p=1

  9. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    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
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    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
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    so any tree with P>1 is 2-chromatic

  12. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    |dw:1442977242648:dw|

  13. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    i feel like this induction is not complete

  14. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    thats not induction, just showing it for convincing ourselves first

  15. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    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
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    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
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    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
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    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
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    okay i see what u mean

  20. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    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
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    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
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    |dw:1442978241263:dw|

  23. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    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
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  25. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  26. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    i can do 2 cases

  27. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  28. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    i think it might get messy..

  29. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    ya theres gotta be a better way

  30. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    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
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    oh wait i can!

  32. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    nvm i cant

  33. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    |dw:1442978612649:dw|

  34. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    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
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    okay i have an idea

  36. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    say A is connected to multiple like u did there

  37. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    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
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    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
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    u must be able to right!!

  40. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    this is my idea in a diagram

  41. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    |dw:1442979234709:dw|

  42. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    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
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    |dw:1442979350004:dw|

  44. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    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
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  46. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    and that case is very easy to prove

  47. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    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
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    would this work?

  49. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    that looks rather complicated but the construction definitely works!

  50. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  51. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    i have a better idea

  52. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    okay go on

  53. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    it is simple

  54. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    lets just make a choice of which vertex we remove

  55. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    oh omg lol xD

  56. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    ya okay that is done

  57. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  58. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    yep

  59. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    how do you know a leaf vertex always exists ?

  60. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    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
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    looks neat !

  62. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    thanks a lot for your help

  63. Not the answer you are looking for?
    Search for more explanations.

    • Attachments:

Ask your own question

Sign Up
Find more explanations on OpenStudy
Privacy Policy

Your question is ready. Sign up for free to start getting answers.

spraguer (Moderator)
5 → View Detailed Profile

is replying to Can someone tell me what button the professor is hitting...

23

  • Teamwork 19 Teammate
  • Problem Solving 19 Hero
  • You have blocked this person.
  • ✔ You're a fan Checking fan status...

Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.