If we have a graph $G$ with vertices $1,2,.....,100$ and two vertices $i$ and $j$ be adjacent if one of them divides the other. I am trying to find the number of covering vertices.
The answer for this question says that the number of independent edges is equal to the number of covering vertices, which is at least I think is the Konig theorem for bipartite graphs https://en.wikipedia.org/wiki/K%C5%91nig%27s_theorem_(graph_theory) and here the answer is = $75$.
So, is this question solved by applying this theorem or the idea behind is completely different? I got completely buggered by it, as the number $1$ divides everything so, it doesn't make sense to me that it is bipartite, but maybe I missed something.
The vertices $\{1,2,4\}$ induce a $K_3$ subgraph:
Thus, it is not bipartite. I'm not sure what this has to do with a maximum-sized independent edge set, but I find one below.
There are $10$ vertices only adjacent to $1$ (the primes $p$ such that $2p>100$), namely $\{53, 59, 61, 67, 71, 73, 79, 83, 89, 97\}$, so an independent edge set cannot include at least $9$ of these vertices, so has size at most $45$.
I found one of size $44$ using a semi-random computerized search:
$$\begin{array}{lllll} [1, 53] & [2, 62] & [3, 87] & [4, 36] & [5, 85] \\ [6, 72] & [7, 77] & [8, 56] & [9, 63] & [10, 20] \\ [11, 55] & [12, 84] & [13, 65] & [14, 28] & [15, 45] \\ [17, 51] & [18, 54] & [19, 57] & [21, 42] & [22, 66] \\ [23, 69] & [25, 75] & [27, 81] & [29, 58] & [30, 60] \\ [31, 93] & [32, 96] & [33, 99] & [37, 74] & [41, 82] \\ [43, 86] & [47, 94] & [24, 48] & [26, 52] & [16, 64] \\ [34, 68] & [35, 70] & [38, 76] & [39, 78] & [40, 80] \\ [44, 88] & [46, 92] & [49, 98] & [50, 100] \end{array}$$
To prove that a $45$-edge independent edge set does not exist...
We choose the edge $[1, 53]$, and delete the vertices $\{1, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97\}$. In the resulting $89$-vertex graph, the vertices $\{37, 41, 43, 47\}$ have degree $1$, so we choose the edges $[37,74]$, $[41,82]$, $[43,86]$, and $[47,94]$. We then delete the vertices $\{37, 41, 43, 47, 74, 82, 86, 94\}$.
In the resulting $81$-vertex graph, we have the induced paths
We choose the edges $[ 29, 58 ]$, $[ 3, 87 ]$, $[ 2, 62 ]$, and $[ 31, 93 ]$, as other choices are either no more efficient or do not "use" two vertices (there's bunch of cases to consider). We delete the vertices $\{2,3,29,31,58,62,87,93\}$, giving a $73$-vertex graph.
This then leaves $\{51, 57, 69\}$ as degree-$1$ vertices, so we choose the edges $[17,51]$, $[19,57]$, and $[23,69]$, and we delete the vertices $\{17,19,23,51,57,69\}$, giving a $67$-vertex graph.
This then leaves $\{34, 38, 46, 85, 95\}$ as degree-$1$ vertices. Both $85$ and $95$ are adjacent to $5$, so we can't use both of them. So we choose the edges $[34,68]$, $[38,76]$, $[46,92]$, and $[5,85]$, and delete the vertices $\{5,34,38,46,68,76,85,92\}$, giving a $58$-vertex graph. (Vertex $95$ goes unused.)
This then leaves $\{55, 65\}$ as degree-$1$ vertices, so we choose the edges $[11,55]$, $[13,65]$, and delete the vertices $\{11,13,55,65\}$, giving a $54$-vertex graph.
This then leaves $\{39, 77, 91\}$ as degree-$1$ vertices. Both $77$ and $91$ are adjacent to $7$, so we can't use both of them. Thus there are at least $11$ vertices that don't participate in any independent edge set.