I prefer computer typed answer because I could not understand bad hand writing.
ID: 3785463 • Letter: I
Question
I prefer computer typed answer because I could not understand bad hand writing.
Also, if you try to answer only part of question for taking your score, I will report you to Chegg.
Please do not take my question for free. The question is related to 'Graph Theory and Non-Enumerative Combinatorics'
Thank you in advance and I apologize for being aggressive because of many free question takers.
Let G be a simple graph. Let n V (G)l be the number of vertices of G. Assume that IE (G)I n (n 2) /4. (In other words, assume that G has less than n (n 2) /4 edges.) Prove that there exist three distinct vertices a, b and c of G such that none of ab, bc and ca are edges of G.Explanation / Answer
Simple Graph
A graph with no loops or multiple edges is called a simple graph. We specify a simple graph by its set of vertices and set of edges, treating the edge set as a set of unordered pairs of vertices and write e = uv (or e = vu) for an edge e with endpoints u and v.
|V|= degree of the graph G i.e., no. of vertices
|E|= size of graph G i.e., no. of edges.
When u and v are endpoints of an edge, they are adjacent and are neighbors.
Proof:
This is easy to prove by induction. If n = 2, zero edges are required, and 2(2 2)/4 = 0. Assume that a simple graph with k vertices has k(k 2)/4. When we add the (k + 2)nd vertex, we need to connect it to the k original vertices, requiring k additional edges. We will then have k(k 2)/4 + k = (k + 2)((k + 2) 2)/4 vertices.