# Mathematics of the upper bound for the encoded input of an instance Kruskal’s MWST problem

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.

1. Assign integers $$1$$ through $$m$$ to the nodes.

2. Begin the code with the value of $$m$$ in binary and the weight limit $$W$$ in binary, separated by a comma.

3. 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$$