Results 1 to 3 of 3

Math Help - Number of subgraphs within a complete graph

  1. #1
    Newbie
    Joined
    Apr 2013
    From
    United States
    Posts
    6

    Number of subgraphs within a complete graph

    How many subgraphs with at least one vertex does K3 (a complete graph with 3 vertices) have?
    I know that K3 is a triangle with vertices a, b, and c. From asking for help elsewhere I was told the formula for the number of subgraphs in a complete graph with n vertices is 2^(n(n-1)/2)

    In this problem that would give 2^3 = 8.

    However from trying to draw all the subgraphs out by hand using this definition: All the edges and vertices of G might not be present in S; but if a vertex is present in S, it has a corresponding vertex in G and any edge that connects two vertices in S will also connect the corresponding vertices in G. All of these graphs are subgraphs of the first graph.

    I was up to 14 subgraphs. From what I understand, the graph itself is a subgraph of K3 (1), the graph with 3 vertices and no edges is a subgraph of K3 (2), a by itself is a subgraph of K3 (3), b by itself is a subgraph of K3 (4), c itself is a subgraph of K3 (5), a and b connected is a subgraph of K3(6), a and c connected is a subgraph of K3(7), a and b by themselves are a subgraph of K3 (8), a and c by themselves are subgraph of K3 (9), etc. I'm failing to understand why some of the graphs I listed are not subgraphs of K3, since they either preserve some of the vertices in S, and any edges in the subgraphs listed are also preserved in K3.

    Any help is greatly appreciated.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1

    Re: Number of subgraphs within a complete graph

    Quote Originally Posted by JK94 View Post
    How many subgraphs with at least one vertex does K3 (a complete graph with 3 vertices) have?
    I know that K3 is a triangle with vertices a, b, and c. From asking for help elsewhere I was told the formula for the number of subgraphs in a complete graph with n vertices is 2^(n(n-1)/2)
    In this problem that would give 2^3 = 8.

    Do you understand the logic behind the formula 2^{\frac{n(n-1)}{2}}~?

    That is the number of subsets of a set of \binom{n}{2} which is the number if edges in \mathcal{K}_n.

    This 2^3 is correct.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Apr 2013
    From
    United States
    Posts
    6

    Re: Number of subgraphs within a complete graph

    Quote Originally Posted by Plato View Post
    Do you understand the logic behind the formula 2^{\frac{n(n-1)}{2}}~?

    That is the number of subsets of a set of \binom{n}{2} which is the number if edges in \mathcal{K}_n.

    This 2^3 is correct.
    I understand that formula and I understand that it applies here as well. However I am simply trying to figure out why some of those relationships I listed are NOT sub-graphs. It seems to me they satisfy the conditions needed for a sub-graph-- namely that "All the edges and vertices of G might not be present in K; but if a vertex is present in K, it has a corresponding vertex in G and any edge that connects two vertices in S will also connect the corresponding vertices in G."
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Finding the subgraphs of a simple graph.
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 4th 2012, 05:15 PM
  2. Wheel graph and complete graph
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: September 29th 2012, 05:56 PM
  3. Graph Theory / Chromatic Number of a Complete Graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 15th 2011, 09:59 AM
  4. Minimum number to remove from a complete graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 14th 2010, 03:11 PM
  5. number of subgraphs in a complete graph
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 29th 2010, 11:04 AM

Search Tags


/mathhelpforum @mathhelpforum