A community for students.
Here's the question you clicked on:
 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, (Hintuse 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,
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, (Hintuse 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

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.1Inducting on P means, you need to show that the statement is true for all \(P\in \mathbb{N}\).

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.11) 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\)

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.1why not simply take base case as \(P=1\)

dan815
 one year ago
Best ResponseYou've already chosen the best response.1that doesnt have diameter 3

dan815
 one year ago
Best ResponseYou've already chosen the best response.1oops ignore that im mixing up questions now

dan815
 one year ago
Best ResponseYou've already chosen the best response.1my 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
 one year ago
Best ResponseYou've already chosen the best response.1Intuitively, 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
 one year ago
Best ResponseYou've already chosen the best response.1so any tree with P>1 is 2chromatic

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.1dw:1442977242648:dw

dan815
 one year ago
Best ResponseYou've already chosen the best response.1i feel like this induction is not complete

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.1thats not induction, just showing it for convincing ourselves first

dan815
 one year ago
Best ResponseYou've already chosen the best response.1so 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
 one year ago
Best ResponseYou've already chosen the best response.1For 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
 one year ago
Best ResponseYou've already chosen the best response.1nvm i guess its fine ill just state that the statement if X(T_p) <=2 for all nonisomorphic trees of T_p

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.1Keep 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
 one year ago
Best ResponseYou've already chosen the best response.1so 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
 one year ago
Best ResponseYou've already chosen the best response.1Yes, but it doesn't work exactly... we still need to tweak a bit.. let me give u an example where it fails

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.1dw:1442978241263:dw

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.1suppose you remove the vertex \(A\), then color the rest of tree what color does the vertex \(A\) gets when you stitch it back ?

dan815
 one year ago
Best ResponseYou've already chosen the best response.1oh i see if we remove A then we cant use that argument

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.1yeah there should be a better way to approach this... this removing and adding thingy may not work

dan815
 one year ago
Best ResponseYou've already chosen the best response.1either you have a vertex connected to multiple vertices or you have a vertex connected to just 1 vertex

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.1i think it might get messy..

dan815
 one year ago
Best ResponseYou've already chosen the best response.1ya theres gotta be a better way

dan815
 one year ago
Best ResponseYou've already chosen the best response.1theres 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

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.1dw:1442978612649:dw

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.1There is no way to connect back the A w/o using a third color so the previous idea is not going to work

dan815
 one year ago
Best ResponseYou've already chosen the best response.1say A is connected to multiple like u did there

dan815
 one year ago
Best ResponseYou've already chosen the best response.1then 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
 one year ago
Best ResponseYou've already chosen the best response.1that 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
 one year ago
Best ResponseYou've already chosen the best response.1u must be able to right!!

dan815
 one year ago
Best ResponseYou've already chosen the best response.1this is my idea in a diagram

dan815
 one year ago
Best ResponseYou've already chosen the best response.1once 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
 one year ago
Best ResponseYou've already chosen the best response.1then 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
 one year ago
Best ResponseYou've already chosen the best response.1in this way since there are no cycles you must remove a point from the end where it only has 1 degree

dan815
 one year ago
Best ResponseYou've already chosen the best response.1and that case is very easy to prove

dan815
 one year ago
Best ResponseYou've already chosen the best response.1since 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

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.1that looks rather complicated but the construction definitely works!

dan815
 one year ago
Best ResponseYou've already chosen the best response.1ya that looks like a lot to write in this one proof lol

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.1i have a better idea

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.1lets just make a choice of which vertex we remove

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.1simply remove a "leaf vertex", the problem is solved :)

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.1how do you know a leaf vertex always exists ?

dan815
 one year ago
Best ResponseYou've already chosen the best response.1well 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

dan815
 one year ago
Best ResponseYou've already chosen the best response.1thanks a lot for your help
Ask your own question
Sign UpFind more explanations on OpenStudy
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
 Engagement 19 Mad Hatter
 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.