Strange Graphs

Computer Science Level 4

While trying to come up with one of his stupid Graph Theory problems, Agnishom wrote the following function to generate a random graph:

# returns the edgelist of a graph with `n` vertices
def genGraph(n):
    edgeList = []
    for v in xrange(2,n+1):
        u = random.randint(1,v-1)
        edgeList.append((u,v))
    return edgeList

Chris told Agnishom that this algorithm is not really that great and can generate only a particular class of graphs.

Which of the following is the best way to describe these class?

Complete Graphs Bipartite Graphs Forests Pseudographs Trees

1 solution

Wesley Zumino
Aug 7, 2017

Function $\text{genGraph}(n)$ generates a graph on the integer-labeled nodes $\{1, ..., n\}$ as follows: Starting with node $v=2$ and an empty edge list, each node $v \in \{2, ..., n\}$ is selected in sequence and one node $u$ is randomly selected from among the integers less than $v$ , i.e., $u \in \{1, ..., v-1\}$ , to form edge $e = (v,u)$ , which is then added to the edge list of the graph. Therefore, one edge is generated for each value $v$ considered, so the total number of edges generated is $|\{2, ..., n\}| = n -1$ .

Furthermore, the resulting graph is connected. To see this, proceed inductively on the generated subgraph of the first $v$ nodes $\{1, ..., v\}$ .

In the first iteration for nodes $\{1,2\}$ , $v=2$ and $u$ is randomly selected from $\{1, ..., v-1\} = \{1\}$ . Therefore, edge $(2,1)$ is added to $\text{edgeList} \Rightarrow$ the generated subgraph with nodes $\{1,2\}$ is connected.

In the iteration for nodes $\{1, ..., v\}$ , $v \le n$ , new edge $(v,u)$ is created by randomly choosing a node $u$ in $\{1, ..., v-1\}$ . But by the induction hypothesis, the generated subgraph $\{1, ..., v-1\}$ is connected. Therefore, $v$ is adjacent to a node in a connected subgraph $\Rightarrow$ the subgraph $\{1, ..., v\}$ is connected.

So, function $\text{genGraph}(n)$ generates a connected graph with $n$ nodes and $n-1$ edges. Therefore, the graph must be a $\boxed{ \text{tree} }$ .

Strange Graphs

1 solution

0 pending reports