Results 1 to 1 of 1

Math Help - Graph Theory - Complete graphs and triangles

  1. #1
    Member Jason Bourne's Avatar
    Joined
    Nov 2007
    Posts
    132

    Graph Theory - Complete graphs and triangles

    K_n denotes the complete graph on n vertices

    (a) Show that if the edges of K_6 are all colured either red or blue, then there is either a triangle of red edges or a triangle of blue edges.

    (b) Show that if the edges of K_6 are all coloured either red or blue, and there are at least 10 red edges, then there is a triangle of red edges. Give an exmaple to show that this need not be the case if just 9 edges are red.

    (c) Show, using part(b), that if the edges of K_9 are all coloured either red or blue and there at least 22 red edges, then there is a triangle of red edges.
    -----------------------------------------------
    For part (a) I think its's done by showing that every vertex ,say v, is incident to 5 edges, and at least 3 of these are the same colour, say red. Let (v,v1),(v,v3),(v,v3) be these 3 edges. So any edge between v1,v2 and v3 that is red would make a red triangle. If none are red then there is a blue triangle.

    For the other 2 parts I have no idea how to proceed. Can anyone help me?
    Last edited by Jason Bourne; May 3rd 2009 at 02:18 PM.
    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, 10:59 AM
  2. Graph theory - triangular graphs
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 3rd 2010, 03:35 AM
  3. Complete Bipartite Graphs
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 29th 2010, 01:27 PM
  4. Graph theory problem (critical graphs)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 12th 2009, 04:21 AM
  5. Graph Theory and complete and isolated graphs
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 5th 2009, 12:19 AM

Search Tags


/mathhelpforum @mathhelpforum