Using VertexDelete to remove vertices by degree

Question

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.

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
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?

@DavidG.Stork you mean why this is a "hard" problem, or meaning I can corrupt my graph accidentally? — soandos, Jan 7 '15 at 0:10
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. — David G. Stork, Jan 7 '15 at 0:26

kglr · Accepted Answer · 2018-05-27 07:37:03Z

6

g = Graph[{1 -> 2, 2 -> 3, 3 -> 1, 2 -> 4},   VertexShapeFunction -> "Name"]

enter image description here

VertexDegree[g]
(* {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

answered Jan 7 '15 at 0:16

kglr

228k10 gold badges259 silver badges521 bronze badges

$\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

add a comment |

Szabolcs · Accepted Answer · 2015-01-07 00:28:25Z

4

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.

answered Jan 7 '15 at 0:28

Szabolcs

194k18 gold badges481 silver badges1018 bronze badges

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

add a comment |

2 Answers 2