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:


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

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


    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
    another question.

    what is the independent number/set ?


    looking at that, and a problem from my homework which the answer is 4:

    http://www.nevada.edu/%7Ebaragar/courses/MAT351ex2sample.pdf [Broken]

    problem # 1b finding the independence number

    is the independence set = {b, d, g, f}


    and that is how the answer is 4?
    Last edited by a moderator: May 2, 2017
  6. Mar 30, 2005 #5


    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook