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,

- dan815

- Stacey Warren - Expert brainly.com

Hey! We 've verified this expert answer for you, click below to unlock the details :)

- katieb

I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!

- ganeshie8

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

- 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

hm

Looking for something else?

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

## More answers

- ganeshie8

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

- dan815

that doesnt have diameter 3

- ganeshie8

what diameter

- dan815

oops ignore that im mixing up questions now

- dan815

okay p=1

- 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

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

so any tree with P>1 is 2-chromatic

- ganeshie8

|dw:1442977242648:dw|

- dan815

i feel like this induction is not complete

- ganeshie8

thats not induction, just showing it for convincing ourselves first

- 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

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

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

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

okay i see what u mean

- 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

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

- ganeshie8

|dw:1442978241263:dw|

- 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

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

- ganeshie8

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

- dan815

i can do 2 cases

- dan815

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

- ganeshie8

i think it might get messy..

- dan815

ya theres gotta be a better way

- 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

oh wait i can!

- dan815

nvm i cant

- ganeshie8

|dw:1442978612649:dw|

- 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

okay i have an idea

- dan815

say A is connected to multiple like u did there

- 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

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

u must be able to right!!

- dan815

this is my idea in a diagram

- dan815

|dw:1442979234709:dw|

- 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

|dw:1442979350004:dw|

- 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

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

- dan815

and that case is very easy to prove

- 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

would this work?

- ganeshie8

that looks rather complicated but the construction definitely works!

- dan815

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

- ganeshie8

i have a better idea

- dan815

okay go on

- ganeshie8

it is simple

- ganeshie8

lets just make a choice of which vertex we remove

- dan815

oh omg lol xD

- dan815

ya okay that is done

- ganeshie8

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

- dan815

yep

- ganeshie8

how do you know a leaf vertex always exists ?

- 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

looks neat !

- dan815

thanks a lot for your help

Looking for something else?

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