Here’s another way to create a random tree.

I grow a tree by adding one node at a time, connected completely at random to just one of the existing nodes. Does this create a tree of a given size (number of vertices), drawn uniformly at random from the set of all trees of the given size?

I think so, and I think that the proof should be by induction on the number of nodes.

Is the labelling of the vertices independent of the shape of the tree? i.e., does the tree “look the same” when we pick any of the vertices as root?

set.seed(1234)
Nnodes <- 50
Nedges <- Nnodes - 1
edgeL <- list()
for (i in 2:Nnodes) {
  branch <- sample((i - 1), 1)
  edgeL[[i - 1]] <- c(as.character(branch), as.character(i))
}

library(gRbase)
library(Rgraphviz)
## Loading required package: graph
## Loading required package: grid
library(igraph)
## 
## Attaching package: 'igraph'
## 
## The following objects are masked from 'package:graph':
## 
##     degree, edges
plot(ug(edgeL))

g <- ug(edgeL, result = "igraph")
layout <- layout.auto(g)   ## fix layout for all later graphs of g
g$layout <- layout
plot(g)

Now I want to pick two nodes at random and draw the path from one to the other. I want to colour the nodes appropriately.

g <- ug(edgeL, result = "igraph")
twoNodes <- sample(50, 2, replace = FALSE)
redNode <- twoNodes[1]
greenNode <- twoNodes[2]
path <- get.shortest.paths(g, redNode, greenNode)$vpath[[1]]
colours <- rep("lightblue", Nnodes)
colours[path] <- "orange"
colours[redNode] <- "red"
colours[greenNode] <- "green"
for (i in 1:Nnodes) V(g)[i]$color <- colours[i]
plot(g)

And now the same graph drawn with Rgraphviz

g <- ug(edgeL)
nodes <- buildNodeList(g)
edges <- buildEdgeList(g)
for (i in 1:length(nodes)) nodes[[i]]@attrs$fillcolor <- colours[i]
plot(agopen(g, edges = edges, nodes = nodes, name = "g"))

Now I try to draw this yet again, with the vertices arranged from my randomly chosen “root” downwards. I’ll do this via an excursion to the adjacency matrix representation.

ag <- as(g, "matrix")
ag <- rbind(cbind(ag[path, path], ag[path, -path]), 
            cbind(ag[-path, path], ag[-path, -path]))
gg <- as(ag, "graphNEL")
nodes <- buildNodeList(gg)
edges <- buildEdgeList(gg)
colours <- rep("lightblue", Nnodes)
colours[1:length(path)] <- "orange"
colours[1] <- "red"
colours[length(path)] <- "green"
for (i in 1:length(nodes)) nodes[[i]]@attrs$fillcolor <- colours[i]
plot(agopen(gg, edges = edges, nodes = nodes, name = "gg"))