Results 1 to 1 of 1

Math Help - Graph theory questions

  1. #1
    Newbie
    Joined
    Sep 2008
    Posts
    18

    Graph theory questions

    1. Show that the join of a 3-cycle and a 5-cycle contains no K_6 but that every 2-edge coloring yields a monochromatic triangle.

    2. Let G_1 and G_2 be k-critical graphs with exactly one vertex v in common, and let vv_1 and vv_2 be edges of G_1 and G_2. Show that the graph (G_1-vv_1) U (G_2-vv_2) + v_1v_2 is k-critical.

    3. Show that a connected \alpha-critical graph has no cut vertices. \alpha is the independence number and a graph is
    \alpha-critical if \alpha(G - e) > \alpha(G) for all e in the edge set of G.

    Sorry I forgot that little bit of extra instruction before.
    Last edited by grad444; November 13th 2008 at 10:11 AM. Reason: Left out extra instructions
    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)Prove that graph X is a tree.
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: August 1st 2011, 04:30 AM
  3. Replies: 0
    Last Post: September 25th 2010, 06:59 AM
  4. Graph Theory - Size of a Line Graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: July 26th 2010, 12:15 AM
  5. Graph Theory Questions
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 28th 2008, 03:46 PM

Search Tags


/mathhelpforum @mathhelpforum