Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Graph theory: quick question(s)

  1. Mar 29, 2005 #1
    what's the difference between a subgraph and an induced subgraph?

    looking here:

    http://mathworld.wolfram.com/InducedSubgraph.html

    how is the figure K8 ? isn't that K10 ??

    also, what is a spanning subgraph?
     
  2. jcsd
  3. Mar 29, 2005 #2

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    That's K10.

    If there is an edge in a graph between two vertices in an induced subgraph, then that edge must be in the induced subgraph as well. If you start with a graph and delete only vertices (as well as any edges that share an end with a deleted vertex), you get an induced subgraph. You can also think of this as the maximal subgraph (in the sense of it's edges) containing a given vertex set. A plain old subgraph has no such restrictions on it's edges. If you look at that K10 example, the subgraph consisting of the vertices {1, 2, 3, 5, 7, 10} and NO edges is a subgraph, but not an induced subgraph.

    A spanning subgraph contains all the vertices of your original graph.

    Something for you to think about-what can you say about an induced subgraph that is a spanning subgraph as well?
     
  4. Mar 29, 2005 #3
    oh ok, so a subgraph can contain no edges .... but that is not induced...in order to be induced, it has to be of the original vertex set with edges (that belonged to the edge set of the original graph) ?

    its not a complete graph?
     
  5. Mar 29, 2005 #4
  6. Mar 30, 2005 #5

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    The only spanning induced subgraph of a graph G is G itself.


    Take a subset of vertices of a graph. Look at the corresponding induced subgraph. If it contains no edges, your vertices are independant. If it contains any edges, they are not independant.

    To show the independant number of the graph in your homework is 4 you can do two things:

    Find an independant set of four vertices, this should be easy.

    Next show that every set containing 5 vertices must have an edge between 2 of the vertices. For a hint, can the vertex c be in an independant set with 5 vertices?
     
  7. Mar 30, 2005 #6
    "in order to be induced, it has to be of the original vertex set with edges (that belonged to the edge set of the original graph)?"

    I don't think this is right. You don't need all the vertices from the original graph, just if you take some subest of vertices, you have to include all of the edges that are incident to the nodes.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Graph theory: quick question(s)
  1. Graph theory (Replies: 5)

  2. Graph theory (Replies: 10)

  3. Graph Theory (Replies: 3)

  4. Graph Theory (Replies: 1)

Loading...