Results 1 to 2 of 2

Math Help - induced subgraphs

  1. #1
    Junior Member
    Joined
    Nov 2009
    Posts
    37

    induced subgraphs

    let G=(V,E) be a simple graph with |V|>=2. If every induced subgraph of G is connected, can you identify the graph G?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Dec 2009
    Posts
    4
    G must be a complete graph. Indeed, assume that G is not complete, so there exist at least one edge {a,b} in G'. Let's take subgraph induced by set {a,b}. This subgraph is obviously not connected. Contradiction.
    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, 01:19 PM
  2. Induced Representations
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: April 25th 2010, 10:34 PM
  3. number of subgraphs in a complete graph
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 29th 2010, 12:04 PM
  4. Spanning and Induced Subgraphs
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: December 8th 2009, 02:06 PM
  5. Spanning and Induced Subgraphs
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: May 8th 2008, 01:21 PM

Search Tags


/mathhelpforum @mathhelpforum