I am trying to remove vertices that have degree less than 2, but I think I am missing something basic.

I was hoping that I could use:

VertexDelete[g, VertexDegree[#] < 2 & ]

But it seems that this is not supported in a few ways.

  1. I know that I can operate on one vertex at a time from the examples, but that seems to use pattern matching, rather than a pure function. I tried using _?(VertexDegree[#] < 2 &) instead as the pure function, but there still is a bigger issue
  2. The VertexDegree does not have an overload that just takes a "vertex" object. For that matter, I don't even know what is being matched in the VertexDelete function. Is it the label of the node only?

I sense I am missing something basic about this whole process. Any pointers?

  • $\begingroup$ @DavidG.Stork you mean why this is a "hard" problem, or meaning I can corrupt my graph accidentally? $\endgroup$ – soandos Jan 7 '15 at 0:10
  • $\begingroup$ I successfully deleted VertexDegree < 2 vertices from VertexList[g] and re-inserted the smaller list into a graph using the prior EdgeList[g] and had problems. The answer below, using VertexDelete automatically recomputes the EdgeList, and hence is superior to my approach. Problem solved. $\endgroup$ – David G. Stork Jan 7 '15 at 0:26
g = Graph[{1 -> 2, 2 -> 3, 3 -> 1, 2 -> 4},   VertexShapeFunction -> "Name"]

enter image description here

(* {2, 3, 2, 1} *)

VertexDelete[g, _?(VertexDegree[g, #] < 2 &)]

enter image description here

You can also use KCoreComponents[g, 2] to find the vertices whose vertex degree at least 2 and use it with Subgraph:

Subgraph[g, KCoreComponents[g, 2], VertexShapeFunction -> "Name"]

same picture

| improve this answer | |
  • $\begingroup$ I hate being this close to an answer, but thank you very much. $\endgroup$ – soandos Jan 7 '15 at 0:23
  • $\begingroup$ @soandos, i know the feeling:) Thank you for the accept. $\endgroup$ – kglr Jan 7 '15 at 0:25

You can use

VertexDelete[g, Pick[VertexList[g], VertexDegree[g], d_ /; d < 2]]

which I expect to have better performance, but I haven't benchmarked.

| improve this answer | |
  • 1
    $\begingroup$ On a graph of about ~100K nodes, the other approach takes about a second. If I need more performance, I'll try it out. $\endgroup$ – soandos Jan 7 '15 at 0:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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