Question

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,

Answer 1

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

Answer 2

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\)

Answer 3

hm

Answer 4

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

Answer 5

that doesnt have diameter 3

Answer 6

what diameter

Answer 7

oops ignore that im mixing up questions now

Answer 8

okay p=1

Answer 9

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

Answer 10

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

Answer 11

so any tree with P>1 is 2-chromatic

Answer 12

i feel like this induction is not complete

Answer 13

thats not induction, just showing it for convincing ourselves first

Answer 14

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

Answer 15

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\)

Answer 16

nvm i guess its fine ill just state that the statement if X(T_p) <=2 for all non-isomorphic trees of T_p

Answer 17

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.

Answer 18

okay i see what u mean

Answer 19

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

Answer 20

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

Answer 21

suppose you remove the vertex \(A\),
then color the rest of tree

what color does the vertex \(A\) gets when you stitch it back ?

Answer 22

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

Answer 23

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

Answer 24

i can do 2 cases

Answer 25

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

Answer 26

i think it might get messy..

Answer 27

ya theres gotta be a better way

Answer 28

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

Answer 29

oh wait i can!

Answer 30

nvm i cant