My Math Forum  

Go Back   My Math Forum > College Math Forum > Applied Math

Applied Math Applied Math Forum

LinkBack Thread Tools Display Modes
December 9th, 2009, 06:37 AM   #1
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?
dynas7y is offline  
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.
cknapp is offline  

  My Math Forum > College Math Forum > Applied Math

induced, spanning, subgraphs

Search tags for this page
Click on a term to search for related topics.
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

Copyright © 2019 My Math Forum. All rights reserved.