(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:
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,