dan815
  • dan815
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,
Mathematics
  • Stacey Warren - Expert brainly.com
Hey! We 've verified this expert answer for you, click below to unlock the details :)
SOLVED
At vero eos et accusamus et iusto odio dignissimos ducimus qui blanditiis praesentium voluptatum deleniti atque corrupti quos dolores et quas molestias excepturi sint occaecati cupiditate non provident, similique sunt in culpa qui officia deserunt mollitia animi, id est laborum et dolorum fuga. Et harum quidem rerum facilis est et expedita distinctio. Nam libero tempore, cum soluta nobis est eligendi optio cumque nihil impedit quo minus id quod maxime placeat facere possimus, omnis voluptas assumenda est, omnis dolor repellendus. Itaque earum rerum hic tenetur a sapiente delectus, ut aut reiciendis voluptatibus maiores alias consequatur aut perferendis doloribus asperiores repellat.
katieb
  • katieb
I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!
ganeshie8
  • ganeshie8
Inducting on P means, you need to show that the statement is true for all \(P\in \mathbb{N}\).
ganeshie8
  • 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\)
dan815
  • dan815
hm

Looking for something else?

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

More answers

ganeshie8
  • ganeshie8
why not simply take base case as \(P=1\)
dan815
  • dan815
that doesnt have diameter 3
ganeshie8
  • ganeshie8
what diameter
dan815
  • dan815
oops ignore that im mixing up questions now
dan815
  • dan815
okay p=1
dan815
  • 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
ganeshie8
  • 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
ganeshie8
  • ganeshie8
so any tree with P>1 is 2-chromatic
ganeshie8
  • ganeshie8
|dw:1442977242648:dw|
dan815
  • dan815
i feel like this induction is not complete
ganeshie8
  • ganeshie8
thats not induction, just showing it for convincing ourselves first
dan815
  • 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
ganeshie8
  • 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\)
dan815
  • 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
ganeshie8
  • 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.
dan815
  • dan815
okay i see what u mean
dan815
  • 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
ganeshie8
  • ganeshie8
Yes, but it doesn't work exactly... we still need to tweak a bit.. let me give u an example where it fails
ganeshie8
  • ganeshie8
|dw:1442978241263:dw|
ganeshie8
  • 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 ?
dan815
  • dan815
oh i see if we remove A then we cant use that argument
ganeshie8
  • ganeshie8
yeah there should be a better way to approach this... this removing and adding thingy may not work
dan815
  • dan815
i can do 2 cases
dan815
  • dan815
either you have a vertex connected to multiple vertices or you have a vertex connected to just 1 vertex
ganeshie8
  • ganeshie8
i think it might get messy..
dan815
  • dan815
ya theres gotta be a better way
dan815
  • 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
dan815
  • dan815
oh wait i can!
dan815
  • dan815
nvm i cant
ganeshie8
  • ganeshie8
|dw:1442978612649:dw|
ganeshie8
  • 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
dan815
  • dan815
okay i have an idea
dan815
  • dan815
say A is connected to multiple like u did there
dan815
  • 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
dan815
  • 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
dan815
  • dan815
u must be able to right!!
dan815
  • dan815
this is my idea in a diagram
dan815
  • dan815
|dw:1442979234709:dw|
dan815
  • 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
dan815
  • dan815
|dw:1442979350004:dw|
dan815
  • 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|
dan815
  • dan815
in this way since there are no cycles you must remove a point from the end where it only has 1 degree
dan815
  • dan815
and that case is very easy to prove
dan815
  • 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
dan815
  • dan815
would this work?
ganeshie8
  • ganeshie8
that looks rather complicated but the construction definitely works!
dan815
  • dan815
ya that looks like a lot to write in this one proof lol
ganeshie8
  • ganeshie8
i have a better idea
dan815
  • dan815
okay go on
ganeshie8
  • ganeshie8
it is simple
ganeshie8
  • ganeshie8
lets just make a choice of which vertex we remove
dan815
  • dan815
oh omg lol xD
dan815
  • dan815
ya okay that is done
ganeshie8
  • ganeshie8
simply remove a "leaf vertex", the problem is solved :)
dan815
  • dan815
yep
ganeshie8
  • ganeshie8
how do you know a leaf vertex always exists ?
dan815
  • 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
ganeshie8
  • ganeshie8
looks neat !
dan815
  • dan815
thanks a lot for your help

Looking for something else?

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