I would like to construct graphs that are generated by subsets of the graph edges but that are non necessarily induced subgraphs, so to be able to construct a function that returns all spanning subgraphs of a graph. I thought this could be done with the Subgraph function, but the example below shows that this is not the case.

G = Graph[{1 <-> 2, 1 <-> 3, 2 <-> 3, 2 <-> 4, 3 <-> 4}];

H = Subgraph[G, {1 <-> 2, 1 <-> 3, 2 <-> 4, 3 <-> 4}];

H == G
(* True *)

(However in this example I would like to get the subgraph without the edge 2<->3)

How can I proceed? Do I need to implement the whole construction, or are there pre-implemented functions that I could use?


1 Answer 1

  1. You cannot use == to compare graphs. Do not do this. It may give unexpected results.

  2. Just use Graph[{1 <-> 2, 1 <-> 3, 2 <-> 4, 3 <-> 4}] to get the subgraph containing exactly thes edges. There is no need to refer to the original graph to get this "subgraph" as it's just the collection of the same edges that you specified.

To take a non-induced subgraph and preserve any properties, use IGTakeSubgraph from IGraph/M.

  • $\begingroup$ It does not matter. If you remove the two ";" and look at the output the extra two edges that I don't want is still there. Also, mine was just an example. I would like to contruct in general a function that builds not induced subgraphs. My goal is in fact to use that to implement a function that returns all spanning subgraphs of a given graph. $\endgroup$ Feb 24, 2020 at 8:52
  • 1
    $\begingroup$ @MaurizioMoreschi may be you should rephrase your original question to state that "My goal is in fact to use that to implement a function that returns all spanning subgraphs of a given graph" ? $\endgroup$
    – chris
    Feb 24, 2020 at 8:53
  • $\begingroup$ @chris Thanks, I have added that. However, the rest of the implementation of the function is fine. I just need to construct a function that gives me non-induced subgraphs as intermediate step. $\endgroup$ Feb 24, 2020 at 8:57
  • $\begingroup$ @Szabolcs Ok, I now get how to use your idea in the general case. Sorry, I first partly misinterpreted your answer. $\endgroup$ Feb 24, 2020 at 9:01
  • $\begingroup$ @MaurizioMoreschi My point is that since it is not an induced subgraph you want, there is nothing to induce/generate. There is no need for a function. Just state the edges you want included and that's it. A special function would be warranted for the case when we want to retain attributes. The IGTakeSubgraph function of my IGraph/M package can do this. $\endgroup$
    – Szabolcs
    Feb 24, 2020 at 9:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.