/sci/ - Science & Math

Question for the physics majors here - what are/were your favorite electives? Need to pick some for this semester and can't really make up my mind, would love to learn from your experience.
Don't give a fuck about easy/useful, looking for something interesting.

I know this isn't a homework thread or something, but I came across a problem in my text book I can't seem to figure out. I'd appreciate it if someone could help me out (I don't want people to solve it for me, I really do want an explanation that would help me understand):
Let G = (V, E) be a graph with n nodes, such that the degree of each node is at most d. Prove that there exists in G a set S of independent nodes (meaning, a set that contains no adjacent nodes) so that |S| >= n/(d+1).
I tried proving by induction, but it requires me to split the problem into 3 different cases, and I can only prove it for 2 of them. (the 1st case is when you add a node that doesn't connect with any other node in G, the 2nd is when you add a node that connects with other nodes in G but not nodes in S, and the 3rd which I can't prove is when you add a node that connects with other nodes in G including ones in S).
Any help would be appreciated!