Results 1 to 2 of 2

Math Help - graph 6

  1. #1
    Member
    Joined
    Apr 2008
    Posts
    204

    graph 6

    (a) Prove that if F and H are graphs of order m and n, respectively, then r(F,H) \leq r(m, n).
    (b) Determine r(P_{4}, P_{4}).
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Aug 2009
    Posts
    125
    cheers!

    (a) Every graph F of order m is a subgraph of K_m and Every graph H of order n is a subgraph of K_n. Let p = r(m,n). Then every blue/red coloured K_p contains a blue K_m or a red K_n, so it contains a blue subgraph F or a red subgraph H. This means that r(F,H) \leq r(m,n).

    (b) Firstly note that r(P_4,P_4)>4
    Spoiler:

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

    Then consider K_5 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 a and suppose, without loss of generality, that two of its incident edges, ab and ac, are red. Denote d,e two remaining vertices. If any one of the edges db, dc, eb, ec is red, then this edge together with cab forms a red P_4. If they are all blue, then dbec is a blue P_4. Thus, r(P_4,P_4) = 5
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Graph Theory / Chromatic Number of a Complete Graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 15th 2011, 09:59 AM
  2. Replies: 7
    Last Post: August 5th 2011, 01:30 PM
  3. Replies: 0
    Last Post: September 25th 2010, 05:59 AM
  4. Graph Theory - Size of a Line Graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: July 25th 2010, 11:15 PM
  5. Replies: 1
    Last Post: February 15th 2009, 05:35 AM

Search Tags


/mathhelpforum @mathhelpforum