Results 1 to 10 of 10

Math Help - Graph Theory

  1. #1
    Junior Member
    Joined
    Nov 2008
    Posts
    53

    Graph Theory

    Is it possible to partition k8 into 2 planar subgraphs?

    Any help would be appreciated.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,657
    Thanks
    1613
    Awards
    1
    Here is a theorem relating the number of edges to the number of vertices in a planar graph: V \geqslant 3 \Rightarrow \quad E \leqslant 3V - 6.
    In K_8 there are 28 edges. If you partition that graph into two subgraph you get \left\{ {E_1 ,V_1 } \right\}\,\& \,\left\{ {E_2 ,V_2 } \right\} where \left\{ \begin{gathered} E_1 + E_2 = 28 \hfill \\ V_1 + V_2 = 8 \hfill \\ \end{gathered} \right..
    Now try for a contradiction.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Nov 2008
    Posts
    53
    Thank you very much for your help.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Nov 2008
    Posts
    4
    I am not quite sure about that answer since you dont necesserally have 28 edges for your 2 subgraphs.
    And I (think) have found a example when it works:
    -k4 and k4
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,657
    Thanks
    1613
    Awards
    1
    Quote Originally Posted by davidmccormick View Post
    Is it possible to partition k8 into 2 planar subgraphs?
    Quote Originally Posted by arnaud89 View Post
    I am not quite sure about that answer since you dont necesserally have 28 edges for your 2 subgraphs.

    Yes you do have all 28 edges.
    The question says to partition K_8 into two subgraphs.
    I assume that is using the term partition in the standard way.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Nov 2008
    Posts
    4
    can you not delete some edges when partitioning your graph??

    and why does k4 doesnt work?

    thanks
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,657
    Thanks
    1613
    Awards
    1
    Quote Originally Posted by arnaud89 View Post
    can you not delete some edges when partitioning your graph??
    No you cannot.
    Do you know what it means to have a partition of a set?
    In this case, the partition has two cells, nonempty, disjoint and their union is the graph.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie
    Joined
    Nov 2008
    Posts
    4
    yes I understand that. But surely a subgraph G of H is obtained by deleting some vertices and/or edges.
    so if it cut k8 in the middle , i delete all the crossing edges and i am left with the complete graph on four vertices which is planar.

    Whats wrong with that argument?
    thanks.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,657
    Thanks
    1613
    Awards
    1
    Are you left with two disjoint subgraphs such that their union is K_8?
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Newbie
    Joined
    Jul 2009
    Posts
    8

    sriram.v

    K_8 has 28 edges k_4 + k_4 has 6+6 12 edges

    let the graph k_8 have vertices x1,x2,x3,x4,x5,x6,x7,x8

    consider a
    First graph k_4 with x1,x2,x3,x4 and the edges from x1,x2,x3 to the vertices x5,x6 and x4 to x7,x8

    second graph k_4 with x5,x6,x7,x8 and the edges x4 to the vertices x5,x6 and the edges x1,x2,x3 to x7,x8

    my email id 140580@gmail.com
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Graph theory, bipartite Graph
    Posted in the Math Topics Forum
    Replies: 2
    Last Post: March 10th 2012, 05:47 AM
  2. Graph Theory / Chromatic Number of a Complete Graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 15th 2011, 09:59 AM
  3. (Graph Theory)Prove that graph X is a tree.
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: August 1st 2011, 03:30 AM
  4. Replies: 0
    Last Post: September 25th 2010, 05:59 AM
  5. Graph Theory - Size of a Line Graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: July 25th 2010, 11:15 PM

Search Tags


/mathhelpforum @mathhelpforum