Results 1 to 2 of 2

Math Help - Finding the subgraphs of a simple graph.

  1. #1
    Newbie
    Joined
    Nov 2012
    From
    Surrey
    Posts
    10

    Finding the subgraphs of a simple graph.

    I've been stumped trying to figure out how to solve this question and I've received conflicting advice. I'm wondering which is correct, and how do actually go about solving this question.

    "Let G be a simple graph with m edges and n vertices. How many different subgraphs with n vertices does G have?"

    I'm given the following equation for assistance:

    If G = (V, E) is a graph (directed or undirected), then G_1 = (V_1, E_1) is called a subgraph of G if 0 \neq V_1 \subseteq V and E_1 \subseteq E, where each edge in E_1 is incident with vertices in V_1
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    Nov 2012
    From
    NY
    Posts
    62
    Thanks
    8

    Re: Finding the subgraphs of a simple graph.

    This is a simple combinatorial problem. Each of the $m$ edges may or may not be included in a subgraph. That gives you $2^m$ possibilities. (The assumption is that isomorphism is not taken into consideration.)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. All subgraphs
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: May 12th 2010, 12:19 PM
  2. number of subgraphs in a complete graph
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 29th 2010, 11:04 AM
  3. Spanning and Induced Subgraphs
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: December 8th 2009, 01:06 PM
  4. induced subgraphs
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 3rd 2009, 01:58 AM
  5. Spanning and Induced Subgraphs
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: May 8th 2008, 12:21 PM

Search Tags


/mathhelpforum @mathhelpforum