<< Chapter < Page | Chapter >> Page > |
$\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.
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.
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.
For any induced ${K}_{4}$ subgraph, at most one vertex has degree 3.
Proof: This follows directly from Proposition 4.
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}$ .
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.
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.
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.
Notification Switch
Would you like to follow the 'The art of the pfug' conversation and receive update notifications?