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,

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.

Get our expert's

answer on brainly

SEE EXPERT ANSWER

Get your free account and access expert answers to this and thousands of other questions.

A community for students.

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
See more answers at brainly.com
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.

Get this expert

answer on brainly

SEE EXPERT ANSWER

Get your free account and access expert answers to this and thousands of other questions

Inducting on P means, you need to show that the statement is true for all \(P\in \mathbb{N}\).
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\)
hm

Not the answer you are looking for?

Search for more explanations.

Ask your own question

Other answers:

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

Not the answer you are looking for?

Search for more explanations.

Ask your own question