Thread: graph 6

(a) Prove that if and are graphs of order m and n, respectively, then .
(b) Determine .

cheers!

(a) Every graph of order is a subgraph of and Every graph of order is a subgraph of . Let . Then every blue/red coloured contains a blue or a red , so it contains a blue subgraph or a red subgraph . This means that .

(b) Firstly note that

Spoiler:

Colour one triangle of with red and the rest of edges blue. Is there a red path or a blue path in such coloured graph?

Then consider coloured with blue and red. Each vertex must have at least two red incident edges or at least two blue incident edges. Pick one vertex and suppose, without loss of generality, that two of its incident edges, and , are red. Denote two remaining vertices. If any one of the edges , , , is red, then this edge together with forms a red . If they are all blue, then is a blue . Thus,