There are $20$ vertices in graph $G$ each having a degree $\ge1$. There are $14$ edges in $G$. Prove that there exists $12$ vertices with $6$ edges in $G$.`
I would like to know if my solution was correct, as of today I started learning graph theory:
The existence of $12$ vertices with $6$ edges is equivalent to the existence of $12$ vertices each with degree of $1$ in the subgraph with $12$ vertices. Assume for the sake of contradiction that it isn't possible. Therefore there must be at most $11$ vertices each with a degree of $1$. However, this imply $28 \ge 11*1+9*2=29$. Contradiction.
I think your solution has a little bit problem: How do you show that if there are 12 vertices each of degree 1, then there are 6 edges between these vertices？(The edges may connect to other vertices) Anyway, here is my solution: Divide the graph into connected components, with $a_1, a_2, ..., a_n$ vertices respectively. By the assumption there are no isolated vertices. Then each connected component with $a_i$ vertices have at least $a_i - 1$ edges, so there are total at least $a_1 + a_2 +...+ a_n - n = 20 - n$ edges in the graph, and hence $n$ is at least 6. Then pick 2 vertices which is connected by an edge in each of 6 connected components would do.