Results 1 to 7 of 7
Like Tree2Thanks
  • 1 Post By SlipEternal
  • 1 Post By SlipEternal

Thread: Which complete bipartite graphs are complete?

  1. #1
    Newbie
    Joined
    Mar 2017
    From
    San Marino
    Posts
    18

    Which complete bipartite graphs are complete?

    Hello again, I come with yet another graph theory problem: which complete bipartite graphs are complete?

    This implies that not all bipartite graphs are complete graphs, which I understand, as a complete graph is a graph where each pair of vertices are adjacent, and a bipartite graph can't have two connected vertices from a single set. But then, are no bipartite graph complete graphs?

    A complete bipartite graph will have each vertex from a set connected by a single edge with each vertex of the second set, but this does not make it a complete graph. Will a complete bipartite graph ever be a complete graph?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,502
    Thanks
    2731
    Awards
    1

    Re: Which complete bipartite graphs are complete?

    Quote Originally Posted by MaryLaine View Post
    Hello again, I come with yet another graph theory problem:
    which complete bipartite graphs are complete
    A complete bipartite graph will have each vertex from a set connected by a single edge with each vertex of the second set, but this does not make it a complete graph. Will a complete bipartite graph ever be a complete graph?
    Please read what you post. Does it make sense to you? Which black dogs are black dogs?
    If the question is "When is a bipartite graph a complete graph" that can be answered.
    As usual $\mathcal{K}_{m,n}$ denotes complete bipartite simple graph with $m$ vertices in one partition and the $n$.
    Last edited by Plato; May 10th 2017 at 06:24 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Nov 2010
    Posts
    3,019
    Thanks
    1154

    Re: Which complete bipartite graphs are complete?

    $K_{0,0}, K_{1,0}, K_{0,1}$ are all trivially complete (as the first one is the empty graph, the second and third are both graphs with a single vertex and zero edges).
    $K_{1,1}$ is complete. Try $K_{1,2}$. Nope, that is one edge short of being a complete graph. Any other complete bipartite graph will not also be a complete graph. Only the four mentioned (note that $K_{1,0}$ and $K_{0,1}$ are essentially the same graph, and some professors do not want them listed separately).
    Thanks from MaryLaine
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Mar 2017
    From
    San Marino
    Posts
    18

    Re: Which complete bipartite graphs are complete?

    Quote Originally Posted by Plato View Post
    Please read what you post. Does it make sense to you? Which black dogs are black dogs?
    If the question is "When is a bipartite graph a complete graph" that can be answered.
    As usual $\mathcal{K}_{m,n}$ denotes complete bipartite simple graph with $m$ vertices in one partition and the $n$.
    A complete bipartite graph is not necessarily a complete graph, which I have clarified further in my post...
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Mar 2017
    From
    San Marino
    Posts
    18

    Re: Which complete bipartite graphs are complete?

    Quote Originally Posted by SlipEternal View Post
    $K_{0,0}, K_{1,0}, K_{0,1}$ are all trivially complete (as the first one is the empty graph, the second and third are both graphs with a single vertex and zero edges).
    $K_{1,1}$ is complete. Try $K_{1,2}$. Nope, that is one edge short of being a complete graph. Any other complete bipartite graph will not also be a complete graph. Only the four mentioned (note that $K_{1,0}$ and $K_{0,1}$ are essentially the same graph, and some professors do not want them listed separately).
    Yes, this makes perfect sense! Thanks a bunch!
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,502
    Thanks
    2731
    Awards
    1

    Re: Which complete bipartite graphs are complete?

    Quote Originally Posted by SlipEternal View Post
    $K_{0,0}, K_{1,0}, K_{0,1}$ are all trivially complete (as the first one is the empty graph, the second and third are both graphs with a single vertex and zero edges).
    $K_{1,1}$ is complete. Try $K_{1,2}$..
    It is a gross under-statement to say that there is no standard set of definitions in graph theory.
    I have never seen a definition of a graph that did not stipulate that the set of vertices is nonempty, $\mathcal{V}\ne\emptyset$.
    In any case, the partition of a set never contains an empty set. Therefore, as a result of the definition of a bipartite graph $\mathcal{K}_{m,n}$ both $m\text{ and }n$ are positive integers.
    This an authoritative text book. Use the "lookinside tab" go to basic concepts page. There nonempty sets for vertices are required.

    If anyone knows of a text that allows an empty vertex set, please direct us to it.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Nov 2010
    Posts
    3,019
    Thanks
    1154

    Re: Which complete bipartite graphs are complete?

    Quote Originally Posted by Plato View Post
    It is a gross under-statement to say that there is no standard set of definitions in graph theory.
    I have never seen a definition of a graph that did not stipulate that the set of vertices is nonempty, $\mathcal{V}\ne\emptyset$.
    In any case, the partition of a set never contains an empty set. Therefore, as a result of the definition of a bipartite graph $\mathcal{K}_{m,n}$ both $m\text{ and }n$ are positive integers.
    This an authoritative text book. Use the "lookinside tab" go to basic concepts page. There nonempty sets for vertices are required.

    If anyone knows of a text that allows an empty vertex set, please direct us to it.
    Is the null-graph a pointless concept? | SpringerLink

    No conclusion is reached. I have seen texts that include it and some that dismiss it. You are probably right for bipartite graphs, so only $K_{1,1}$ is both a complete bipartite graph and a complete graph.
    Last edited by SlipEternal; May 10th 2017 at 12:18 PM.
    Thanks from Plato
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Eigenvalues of complete partite Graphs.
    Posted in the Advanced Math Topics Forum
    Replies: 0
    Last Post: Mar 18th 2015, 10:49 AM
  2. Replies: 0
    Last Post: Feb 1st 2013, 01:20 AM
  3. complete bipartite subgraph of a graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Sep 6th 2011, 06:13 PM
  4. Spanning Tree's in the Complete Bipartite Graph
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Mar 26th 2011, 04:33 AM
  5. Complete Bipartite Graphs
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Mar 29th 2010, 01:27 PM

/mathhelpforum @mathhelpforum