5.1 Vizing's conjecture and related graph properties  (Page 4/4)

Proposition 2:

$\left|G\right|\le \delta \left(G\right)\Delta \left(G\right)$ .

Proof: We start by looking at the vertex with the smallest degree, $v_s$ . Since for any vertex $v$ , $N\left(v\right)\cap N\left(v_s\right)\ne \varnothing$ we can say that every vertex is connected to either $v_s$ or a vertex in $N\left(v_s\right)$ . There are $\delta \left(G\right)$ such vertices, having a maximum degree of $\Delta \left(G\right)$ , implying that there are at most $\delta \left(G\right)\Delta \left(G\right)$ vertices in the graph.

Proposition 3 (the lonely neighbor property):

For each edge $(u,v)$ there exists a vertex $w$ such that exactly one of $(w,v)$ or $(w,u)$ is in $E\left(G\right)$ . Assuming $(w,v)$ is in $E\left(G\right)$ then for each vertex $y$ exactly one of $(y,w)$ or $(y,u)$ is in $E\left(G\right)$ .

Proof: Let an edge $(u,v)$ be given. Because our graph is minimal, there exists a vertex $w$ such that $N\left(a\right)\cap N\left(w\right)=b$ for some labels $a,b\in \{u,v\}$ . Without loss of generality assign $a$ to $u$ and $b$ to $v$ . Now suppose for the sake of contradiction that $(w,u)$ is in $E\left(G\right)$ . Then $\{u,v,w\}$ induces a $K_3$ and so there exists $x\in V\left(G\right)\setminus \{u,v,w\}$ such that $\{u,v,w,x\}$ induces a $K_4$ , but then $x\in N\left(u\right)\cap N\left(w\right)=v$ a contradiction. Now let a vertex $y\in V\left(G\right)\setminus \{u,v,w\}$ be given. Suppose both $(y,w)$ and $(y,u)$ are in $E\left(G\right)$ then $y\in N\left(u\right)\cap N\left(w\right)=v$ which is again a contradiction.

Proposition 4:

For any edge $(u,v)\in G$ , at least one of $u,v$ has degree of at least 4.

Proof: Suppose that neither of $u$ nor $v$ have degree of at least 4. It follows from Proposition 1 that $deg\left(u\right)=deg\left(v\right)=3$ . $u$ and $v$ must both be contained in a $K_4$ subgraph. By the lonely neighbor property, there must exist a vertex $w$ such that either $(u,w)\in G$ or $(v,w)\in G$ . This is a contradiction, as desired.

Proposition 5:

For any induced $K_4$ subgraph, at most one vertex has degree 3.

Proof: This follows directly from Proposition 4.

Proposition 5:

If $G(V,E)$ is a graph in $S$ then there are atleast $\frac{\left|E\right|}{6}$ choices of 4-tuples which induce a $K_4$ .

Proof: Each edge is in a $K_4$ and so it must make up at least $\frac{1}{6}$ of a $K_4$ .

Proposition 6:

For any $v\in V\left(G\right)$ , $v$ is contained in at least $\lceil \frac{\text{deg(}v\text{)}}{3}\rceil$ $K_4$ subgraphs.

Proof: Since any $K_4$ subgraph that contains $v$ must contain three other vertices, and $v$ must be adjacent to all of these vertices, there must be $\frac{\text{deg(}v\text{)}}{3}$ induced $K_4$ subgraphs. Since this implies that there may be some uncounted incident edges to $v$ , and that all edges are contained in a $K_4$ subgraph, it follows that $v$ is contained in at least $\lceil \frac{\text{deg(}v\text{)}}{3}\rceil$ $K_4$ subgraphs.

Proposition 7:

In any induced $K_4$ subgraph, at least one vertex must have a minimum degree of 5.

Proof: Let $\{v_1,v_2,v_3,v_4\}\in G$ induce a $K_4$ subgraph. Suppose for the sake of contradiction that $deg\left(v_i\right)\le 4$ , for $i\in \{1,2,3,4\}$ . $K_4$ is not a minimal 3-cover, so without loss of generality, let $v_1$ have degree 4. Since all edges are contained in a $K_4$ subgraph, it follows that two more vertices in our original $K_4$ subgraph ( $\{v_2,v_3\}$ ) must be part of another $K_4$ subgraph, along with $v_1$ , and a fifth vertex, called $v_5$ . $v_4$ cannot have degree of 4, since this would imply that at least one of $\{v_1,v_2,v_3\}$ would have degree more than 5, so it must have degree 3. However, the graph induced by $\{v_1,v_2,v_3,v_4,v_5\}$ is not a minimal 3-cover, so at least one incident edge must be added to $v_5$ . Call the corresponding adjacent vertex $v_6$ . Since $G$ is a 3-cover, there must be a vertex that is adjacent to both $v_3$ and $v_6$ , which implies that we must add an incident edge to at least one of the vertices in $\{v_1,v_2,v_3,v_4\}$ , which leads to a contradiction, as desired.

Conclusion

Future work on this topic could either find a counterexample to the conjecture, or show that there is no counterexample by using bounds to arrive at a contradiction.