Results 1 to 2 of 2

Math Help - Complete Bipartite Graphs

  1. #1
    Newbie
    Joined
    Jan 2010
    Posts
    18

    Complete Bipartite Graphs

    Let G be a bipartite graph with vertex partition \{V_1,V_2\}.

    (a)
    Prove That

    \sum_{x \in V_1} deg(x) = |E| = \sum_{y \in V_2} deg(y)

    (b)
    A graph is k-regular if every vertex has degree k. Prove
    that if G is k-regular with k > 0, then |V_1| = |V_2| (remember that,in this question, G is bipartite with vertex partition \{V_1,V_2\}.)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,607
    Thanks
    1574
    Awards
    1
    Recall that if v\in V_1 then \text{Deg}(v)=\left|V_2\right|.
    So part a follows from that.

    Part b is from the definition of regularity.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. complete bipartite subgraph of a graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 6th 2011, 05:13 PM
  2. Spanning Tree's in the Complete Bipartite Graph
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 26th 2011, 03:33 AM
  3. Bipartite graphs
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 23rd 2010, 01:12 AM
  4. Bipartite Graphs
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: September 23rd 2009, 08:00 AM
  5. SOS - bipartite graphs
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 29th 2006, 11:50 PM

Search Tags


/mathhelpforum @mathhelpforum