I was going through the classic text “Introduction to Automata Theory, Languages, and Computation” by Hofcroft, Ullman and Motwani where I came across the encoding of an instance of Kruskal’s Mininum Weight Spanning Tree ($ MWST$ ) problem so that it could be given as input to a Turing Machine. The encoding is as shown.
The Kruskal’s problem could be couched as: “Given this graph $ G$ and limit $ W$ , does $ G$ have a spanning tree of weight $ W$ or less?”
Let us consider a possible code for the graphs and weight limits that could be the input to the $ MWST$ problem. The code has five symbols, $ 0$ , $ 1$ , the left and right parentheses, and the comma.
Assign integers $ 1$ through $ m$ to the nodes.
Begin the code with the value of $ m$ in binary and the weight limit $ W$ in binary, separated by a comma.
If there is an edge between nodes $ i$ and $ j$ with weight $ w$ , place $ (i, j, w)$ in the code. The integers $ i$ , $ j$ , and $ w$ are coded in binary. The order of $ i$ and $ j$ within an edge, and the order of the edges within the code are immaterial. Thus, one of the possible codes for the graph of Fig. with limit $ W = 40$ is
$ 100, 101000(1, 10, 1111)(1, 11, 1010)(10, 11, 1100)(10, 100, 10100)(11, 100, 10010)$
If we represent inputs to the $ MWST$ problem above, then an input of length $ n$ can represent at most $ O(n/\log n)$ edges. It is possible that $ m$ , the number of nodes, could be exponential in $ n$ , if there are very few edges. However, unless the number of edges, $ e$ , is at least $ m-1$ the graph cannot be connected and therefore will have no $ MWST$ , regardless of its edges. Consequently, if the number of nodes is not at least some fraction of $ n/\log n$ , there is no need to run Kruskal’s algorithm at all we simply say “no there is no spanning tree of that weight.”
I do not understand the mathematics behind the lines which are given in bold. How are they bounding the number of edges by dividing the total input size $ n$ by $ \log n$ . If the number of edges are less then how can the number of node $ m$ be exponential in $ n$