Results 1 to 2 of 2

Thread: graph 6

  1. #1
    Member
    Joined
    Apr 2008
    Posts
    204

    graph 6

    (a) Prove that if $\displaystyle F$ and $\displaystyle H$ are graphs of order m and n, respectively, then $\displaystyle r(F,H) \leq r(m, n)$.
    (b) Determine $\displaystyle 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 $\displaystyle F$ of order $\displaystyle m$ is a subgraph of $\displaystyle K_m$ and Every graph $\displaystyle H$ of order $\displaystyle n$ is a subgraph of $\displaystyle K_n$. Let $\displaystyle p = r(m,n)$. Then every blue/red coloured $\displaystyle K_p$ contains a blue $\displaystyle K_m$ or a red $\displaystyle K_n$, so it contains a blue subgraph $\displaystyle F$ or a red subgraph $\displaystyle H$. This means that $\displaystyle r(F,H) \leq r(m,n)$.

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

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

    Then consider $\displaystyle 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 $\displaystyle a$ and suppose, without loss of generality, that two of its incident edges, $\displaystyle ab$ and $\displaystyle ac$, are red. Denote $\displaystyle d,e$ two remaining vertices. If any one of the edges $\displaystyle db$, $\displaystyle dc$, $\displaystyle eb$, $\displaystyle ec$ is red, then this edge together with $\displaystyle cab$ forms a red $\displaystyle P_4$. If they are all blue, then $\displaystyle dbec$ is a blue $\displaystyle P_4$. Thus, $\displaystyle 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: Nov 15th 2011, 09:59 AM
  2. Replies: 7
    Last Post: Aug 5th 2011, 01:30 PM
  3. Replies: 0
    Last Post: Sep 25th 2010, 05:59 AM
  4. Graph Theory - Size of a Line Graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Jul 25th 2010, 11:15 PM
  5. Replies: 1
    Last Post: Feb 15th 2009, 05:35 AM

Search Tags


/mathhelpforum @mathhelpforum