I am doing a straightforward deletion of a set of vertices in a Tree using Mathematica.

     a = CompleteKaryTree[5, DirectedEdges -> True];
     b = TreePlot[a, VertexLabeling -> True]

The tree looks fine.

However, I want to delete some vertices:

     c = VertexDelete[a, {11, 12}];
     d = TreePlot[c, VertexLabeling -> True]

Although I deleted Vertices 11 and 12, the resultant graph still contains vertices labeled 11 and 12. Is there a bug in VertexDelete?


No, this is not a bug in VertexDelete.

Some background first:

TreePlot, along with GraphPlot, is an old function that predates the introduction of Graph objects. Consider it deprecated that is only kept for backwards compatibility.

The proper way to display vertex labels for a Graph object is

g = CompleteKaryTree[5, DirectedEdges -> True, VertexLabels -> "Name"]

Or if you already have g, then you can use

SetProperty[g, VertexLabels -> "Name"]

Or even use (since Mathematica 10)

Graph[g, VertexLabels -> "Name"]

If g was originally created using CompleteKaryTree then this latter form will not work. That is a bug, but completely unrelated to your question.

With the standard, modern way of displaying graphs you can observe that VertexDelete does give a correct result:

VertexDelete[g, {11, 12}]

Mathematica graphics

Why does TreePlot appear to show this graph incorrectly then?

That's because as I said TreePlot was introduced in version 6 when there were no Graph objects. The tree was instead specified as a list of rules. It was not even possible to plot a forest (i.e. multiple unconnected trees, like your example) with it. TreePlot is still included in the current version for the sake of backwards compatibility: so Mathematica can still run old programs which do not use Graph.

TreePlot was also updated to have some support for Graph objects, but this support is incomplete. The names of vertices are not preserved when converting a Graph to a TreePlot compatible form. What is displayed with VertexLabeling -> True is not the names of vertices in this case, but their indices.

In short:

Do not use old deprecated graph functions with new Graph objects. Use the new functionality: everything that TreePlot could do has a newer alternative.

There are several GraphLayouts especially suitable for trees:

SetProperty[VertexDelete[g, {11, 12}], 
 GraphLayout -> "LayeredEmbedding"]

Mathematica graphics

The others are "LayeredDigraphEmbedding", "BalloonEmbedding" and "RadialEmbedding". The root vertex can also be specified, please check here.

The IGraph/M package has a few additional tree-specific layouts which may give slightly different results than Mathematica's builtin.

| improve this answer | |

There is no bug. Vertices 11 and 12 were indeed deleted from a.

a = CompleteKaryTree[5, DirectedEdges -> True];

{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31}

c = VertexDelete[a, {11, 12}];

{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31}

When you plot two trees, vertices 5 and 6 each direct to two vertices in a and only to one vertex in c. The labeling of vertices on the plot has changed but the vertices didn't.

TreePlot[a, VertexLabeling -> True]
TreePlot[c, VertexLabeling -> True]

enter image description here enter image description here

| improve this answer | |
  • $\begingroup$ @Szabolcs, Pavlo Fesenko. Thanks for your time. Your answers were very informative! $\endgroup$ – Murali Jan 31 '16 at 15:31

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.