Help with graph induction question?

HINT: Suppose not, and let $G$ be a minimal counterexample. Let $G$ have $2m$ vertices, each of degree greater than $m$. Let $v$ be any vertex of $G$, and let $w$ be any vertex such that $vw$ is an edge. Let $G'$ be the graph that remains after you remove the vertices $v$ and $w$ and all edges incident at them. Use the fact that $G$ contains no triangle to show that for each vertex $u$ of $G'$, $$\deg_{G'}(u)\ge\deg_G(u)-1\ge m-1$$ and get the contradiction that $G$ wasn’t actually a minimal counterexample.

(You can recast this as a proof by induction on $m$ in the usual style, if you want; it’s the same proof either way, with almost identical details.)

Proof by induction means proving a base case and then proving that if true for x it is true for x +1. Since we are only interested in in even numbers of vertices that would mean proving that if true for n vertices it is also true for n + 2 vertices.

Given graph G with n vertices where n is even and greater than 3 and every vertex has (n/2)+1 edges.

Our base case is n = 4. With n = 4 each vertex has (4/2)+1 = 3 edges. This means that every vertex is connected to every other vertex by an edge. Thus any combination of 3 vertices will be a 3 cycle.

Inductive step. If true for n = k then true for n = k+2.

With k vertices: each of the k vertices has (k/2)+1 edges attached to it and each edge connects 2 vertices so the graph as a whole has (k((k/2)+1))/2 total edges in it. A graph with k+2 vertices will increase the number of edges in the graph by (((k+2)(((k+2)/2)+1))/2) - ((k((k/2)+1))/2). (the number in the larger graph - number in the smaller graph). We can simplify this to k+2 additional edges in the graph.

Since our graph with k vertices had a 3-cycle (our inductive assumption) we must remove at least one of those edges from that graph. Each vertex, except the 2 new ones and the two connected by the edge we removed, need one new edge attached to them. The two vertices that were connected by the edge we removed need 2 new edges, and the two new vertices will each need ((k+2)/2)+1 new edges.

Adding the edge removed from the graph with k vertices to the number of additional edges that we have to add, we need to add k+3 edges to the graph. If we add a new edge between any of the original k vertices we will be creating a 3-cycle. (we have accepted as true that with all the edges in a graph of k a 3-cycle was created, even if the edge removed broke the only one 3-cycle then a new one would be formed by placing an edge somewhere else among the original k vertices). Since we can't place a new edge between any 2 of the original k vertices each of them must connect to one of the new vertices. If we connect each of the original k vertices to one of the new vertices we have placed k of the edges and have 3 edges left to place. The two vertices that were connected by the edge we removed and the two new vertices are the only ones that can accept a new edge. Each of the two vertices that were part of the orignal k vertices can only accept one edge and each is connected to at least one of the two new vertices. We are left with 4 vertices we can connect edges to and 5 edges connecting those 4 vertices (the 3 we haven't placed plus the 2 already placed between the old and new vertices) plus we can't connect the two old vertices together. 5 edges placed among 4 vertices means that while 2 of the 4 are connected to only two other vertices the other 2 vertices are connected to all 3 of the other vertices and those two will create an 3 cycle with on of the other two.

Proof complete.

Someone else may be able to write it out clearer but it is all here.