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 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Spanning proof  mathnub  Linear Algebra  1  September 13th, 2013 08:52 AM 
Graphs without induced subgraphs with 3/4 edges?!  MageKnight  Applied Math  0  January 15th, 2013 06:59 AM 
Induced Subgraphs (Graph Theory)  Kramer  Real Analysis  1  August 2nd, 2012 09:39 AM 
Induced emf problem  dynas7y  Physics  2  June 10th, 2010 05:18 AM 
I wrote this in a drug induced trance...what does it mean?  3Arctan1  New Users  21  October 9th, 2009 03:57 PM 