Results 1 to 1 of 1

Thread: 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 $\displaystyle K_6$ but that every 2-edge coloring yields a monochromatic triangle.

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

    3. Show that a connected $\displaystyle \alpha$-critical graph has no cut vertices. $\displaystyle \alpha$ is the independence number and a graph is
    $\displaystyle \alpha$-critical if $\displaystyle \alpha$(G - e) > $\displaystyle \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; Nov 13th 2008 at 09: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: Nov 15th 2011, 09:59 AM
  2. (Graph Theory)Prove that graph X is a tree.
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Aug 1st 2011, 03:30 AM
  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. Graph Theory Questions
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Oct 28th 2008, 02:46 PM

Search tags for this page

Click on a term to search for related topics.

Search Tags


/mathhelpforum @mathhelpforum