My Math Forum Spanning and Induced Subgraphs

 Applied Math Applied Math Forum

 December 9th, 2009, 06:37 AM #1 Newbie   Joined: Dec 2009 Posts: 4 Thanks: 0 Spanning and Induced Subgraphs Let G be a complete graph on n vertices. a. How many spanning subgraphs does G have? b. How many induced subgraphs does G have?
 December 9th, 2009, 06:54 AM #2 Senior Member   Joined: Oct 2007 From: Chicago Posts: 1,701 Thanks: 3 Re: Spanning and Induced Subgraphs Do the spanning graphs need to be connected? Are the vertices labeled? (i.e. are two isomorphic graphs with different vertices considered the same?) An induced subgraph will be complete. How many complete graphs with at most n vertices are there? In any case, for the first question, you are just removing edges and for the second, just vertices. Count the ways to this.

 Tags induced, spanning, subgraphs

,

,

,

,

,

,

,

,

,

,

,

# spanning subgraph and induced

Click on a term to search for related topics.
 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post mathnub Linear Algebra 1 September 13th, 2013 08:52 AM MageKnight Applied Math 0 January 15th, 2013 06:59 AM Kramer Real Analysis 1 August 2nd, 2012 09:39 AM dynas7y Physics 2 June 10th, 2010 05:18 AM 3Arctan1 New Users 21 October 9th, 2009 03:57 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top