Your proof is incorrect. A spanning tree exists if and only if the graph is connected. $deg(u) \ge 2 \not\implies G$ is connected. You haven't proved that the graph is connected.
Example:
Consider this graph with 6 nodes and 6 edges:
$1-2
, 2-3
, 3-1
, 4-5
, 5-6
, 6-1$
Hint 1:
Try to use the inductive hypothesis on each connected component of the graph.
Hint 2:
Use the fact that a connected component with $r$ number of nodes must have $\ge r-1$ edges.
Hint 3:
Use the fact that the sum of the edges of all connected components must be equal to $n$, the number of nodes in the graph.
Hint 4:
If there are $r \ge 1$ connected components, then the total number of edges in these connected components is $ m \ge n - r$. But we know that $m = n$ which implies that at least one connected component with $l$ number of nodes has more than $l-1$ edges. Now use the inductive hypothesis.
Step 1. Suppose that any two vertices have an odd number of common neighbors. For an arbitrary vertex $v$, look at the subgraph induced by the neighbors of $v$. All degrees in this subgraph are odd.
Let $G$ be the original graph, and let $H$ be the induced subgraph of neighbors of $v$. If $xy$ is an edge of $H$, then back in $G$, $y$ is a common neighbor of $x$ and $v$: it's a neighbor of $x$ because $xy$ is also an edge of $G$, and it's a neighbor of $v$ because everything in $H$ is.
Conversely, whenever $x$ is a neighbor of $v$ and $y$ is a common neighbor of $x$ and $v$, $xy$ is an edge of $H$.
So for some vertex $x$ in $H$, the number of edges $xy$ is the number of common neighbors of $x$ and $v$; by assumption, this is odd.
Step 2. ...and hence the degree of $v$ is even.
You're right; this is because of the handshake lemma, applied to $H$. We know $H$ has an even number of vertices of odd degree; all of $H$'s vertices have odd degree, so $H$ has an even number of vertices. But the number of vertices in $H$ is precisely the degree of $v$.
Step 3. Let us count walks of length $2$ beginning at $v$...
A walk beginning at $v$ is any triple $(v,w,x)$ where $vw$ and $wx$ are edges of $G$. Why is the number of walks even? For every choice of $w$, we have $\deg w$ many choices for $x$. So the number of walks is $\sum_{w} \deg w$, where the sum ranges over all $w$ adjacent to $v$. Each term in the sum is even, so the number of walks is even.
We can also count the walks in a different way. We have:
- walks $(v,w,v)$ that come back to $v$. There are $\deg v$ of these: an even number.
- walks $(v,w,x)$ for another vertex $x \ne v$. There are $|V(G)| - 1$ choices of $x$. For each $x$, the number of choices for $w$ is the number of common neighbors that $v$ and $x$ have, which is odd by assumption.
If $|V(G)|$ were even, then there would be an odd number of walks of the second kind: $|V(G)|-1$ is an odd number of choices, and each results in an odd number of options for $w$. But then there's an odd number of walks, and we've already proved that there's an even number of walks.
So $|V(G)|$ must be odd, and we're done.
Best Answer
I do not quite think that your approach can provide a contradiction.
A set of vertices, no two of which are joined to each other, is called an independent set. I will use this terminology. So our question is this : in a graph with hundred vertices and maximum degree four, we can find an independent set of size $20$.
Here's a better and easier way to do things. We will provide an algorithm that will find an independent set of size $20$ within the setup. Start with an empty set $S$.
Take any vertex $v$ in the graph, and add it to $S$.
Remove $v$ and its neighbours from the graph, and repeat the above step with the new graph.
End when there are no vertices left.
Now, what is the size of $S$? Note that at each step, at most five vertices removed at each step,since you remove the chosen vertex $v$ and its neighbours, of which there can't be more than four. Now, there are hundred vertices, which means that the steps given above repeat at least $20$ times. For each step, some new vertex is added to $S$. It follows that $S$ has at least $20$ elements.
Now, $S$ is an independent set. To see this, if two vertices $A$ and $B$ are in $S$ and are connected by an edge, then if (without loss of generality) $A$ was chosen before $B$ as a member of $S$ by the algorithm, then $B$ would have been removed from the graph, so it cannot have been made a member of $S$.
Consequently, $S$ is an independent set of size $20$.
Use the above approach for a generalization :
I am not sure that one can improve the number $\frac n{d+1}$. You can test this by trying trivial examples.