# Proof of graph theory on dominating sets

Let G be a graph with 3n vertices, with the property that every pair of vertices has codegree at least 1. That is, ∀x∀y∃z such that xz and yz are both edges. Show that G has a dominating set of size n.

I do not understand the following proof;i dont understand the part "this is at most $$e^{−np2}≤ e^{− log n} = n^{−1}$$. Therefore, a union bound over the n choices of v produces the result." and also the neighbor part; if anyone could explain what the last paragraph of the proof means that would be great thanks.

Proof:

The codegree condition implies that the diameter of the graph is at most 2. We prove that every $$n$$-vertex graph with diameter $$\leq 2$$ has a dominating set (a subset $$S$$ of vertices such that every other vertex is either in, or has a neighbor in $$S$$) of size only $$\leq\sqrt{nlogn}+1$$

To see this, let $$p =\sqrt{log n/n}$$

Observe that since the diameter is at most 2, if any vertex has degree ≤ np, then its neighborhood already is a dominating set of suitable size. Therefore, we may assume that all vertices have degree strictly greater than np. It feels “easy” to find a small dominating set in this graph because all degrees are high. Consider a random sample of np vertices (selected uniformly at random, with replacement), and let S be their union. Note that $$|S| \leq np$$. Now the probability that a particular fixed vertex $$v$$ fails to have a neighbor in S is strictly less than $$(1 −p)^np$$, because we need each of np independent samples to miss the neighborhood of v. This is at most $$e^{−np2}≤ e^{− log n} = n^{−1}$$. Therefore, a union bound over the $$n$$ choices of $$v$$ produces the result.

• What is that from? If you are quoting someone else's words, you must give them due credit. – bof May 12 '19 at 4:49
• Also, if one of us happens to have access to a copy of that textbook, that may make it easier to answer your question. – bof May 12 '19 at 4:50
• its from an online pdf textbook of random graph theory questions – james black May 12 '19 at 5:00
• sorry not exactly a book – james black May 12 '19 at 5:00
• Well how about a link? And it still must have an author. Is it anonymous? – bof May 12 '19 at 5:10

The neighbourhood of $$v$$ has more than $$np$$ vertices, so less than $$n-np$$ out of $$n$$ vertices are not neighbours of $$v$$. Thus the probability that a random vertex is not in the neighbourhood is $$< (1-p)$$, and the probability that none of the $$np$$ random vertices are is $$<(1-p)^{np}$$.
Now $$(1-p)\leq e^{-p}$$ from looking at the graphs, so $$(1-p)^{np}\leq e^{-n^2p}=e^{-\log n}=\frac1n$$.
Since the probability that a particular vertex $$v$$ is not covered is $$<1/n$$, the chance that some vertex is not covered is $$<\frac1n\times n$$ by adding up all the individual probabilities. Since the probability is less than $$1$$, it is possible that this doesn't happen, i.e. you chose a dominating set. So a dominating set must exist.