Skip to main content
added 951 characters in body
Source Link
Fedor Petrov
  • 108.9k
  • 9
  • 264
  • 459

For finite graphs there exists a graph $G$ on $n$ vertices with $\delta(G)\geqslant \lfloor n^2/4\rfloor$. Namely, let $G$ be the disjoint union of two cliques $C_1,C_2$ on $a=\lceil n/2\rceil$ and $b=\lfloor n/2\rfloor$ vertices resp. The vertices of $C_1$ should correspond to disjoint sets $X_1,\ldots,X_a$, the vertices of $C_2$ to disjoint sets $Y_1,\ldots,Y_b$. Any two sets $X_i,Y_j$ should have a common element $p_{ab}$, and they are all distinct since $X_i$'s are disjoint aswell as $Y_j$'s. Therefore the ground set $S$ must contain at least $ab=\lfloor n^2/4\rfloor$ elements.

If I remember well, anythe edge set of theany graph $G$ on $n$ vertices ismay be covered by a disjoint union of at most $\lfloor n^2/4\rfloor$$f(n):=\lfloor n^2/4\rfloor$ cliques (cliques of size 2 and 3 should be enough), that implies $\delta(G)\leqslant \lfloor n^2/4\rfloor$. So this estimate for fixed $n$ is sharp.

The fact I am trying to remember should be provable by induction with removing a vertex with the minimal degree.

Indeed, let $v$ be a vertex of $G$ of minimal degree $d$, $N(v)$ be the set of neighbours of $v$. If $N(v)$ contains at least $d(v)-f(n)+f(n-1)$ disjoint edges, then the edges incident to $v$ may be covered by $f(n)-f(n-1)=\lfloor n/2\rfloor$ triangles and segments, and we may induct. If not, we have $d=\lfloor n/2\rfloor+k$ for some $k>0$, and $N(v)$ contains at most $k-1$ disjoint edges. Choose a maximal collection $\Omega$ of disjoint edges in $N(v)$. We have $k=d-\lfloor n/2\rfloor\leqslant n-1-\lfloor n/2\rfloor\leqslant \lfloor n/2\rfloor$, therefore the exist $w\in N(v)$ not covered by the edges from $\Omega$. This vertex $w$ may be joined with at most $2(k-1)$ vertices in $N(v)$, thus the degree of $w$ does not exceed $2(k-1)+n-d=n-2+k-\lfloor n/2\rfloor<\lfloor n/2\rfloor+k=d$, a contradiction.

For finite graphs there exists a graph $G$ on $n$ vertices with $\delta(G)\geqslant \lfloor n^2/4\rfloor$. Namely, let $G$ be the disjoint union of two cliques $C_1,C_2$ on $a=\lceil n/2\rceil$ and $b=\lfloor n/2\rfloor$ vertices resp. The vertices of $C_1$ should correspond to disjoint sets $X_1,\ldots,X_a$, the vertices of $C_2$ to disjoint sets $Y_1,\ldots,Y_b$. Any two sets $X_i,Y_j$ should have a common element $p_{ab}$, and they are all distinct since $X_i$'s are disjoint aswell as $Y_j$'s. Therefore the ground set $S$ must contain at least $ab=\lfloor n^2/4\rfloor$ elements.

If I remember well, any edge set of the graph on $n$ vertices is a disjoint union of at most $\lfloor n^2/4\rfloor$ cliques (cliques of size 2 and 3 should be enough), that implies $\delta(G)\leqslant \lfloor n^2/4\rfloor$. So this estimate for fixed $n$ is sharp.

For finite graphs there exists a graph $G$ on $n$ vertices with $\delta(G)\geqslant \lfloor n^2/4\rfloor$. Namely, let $G$ be the disjoint union of two cliques $C_1,C_2$ on $a=\lceil n/2\rceil$ and $b=\lfloor n/2\rfloor$ vertices resp. The vertices of $C_1$ should correspond to disjoint sets $X_1,\ldots,X_a$, the vertices of $C_2$ to disjoint sets $Y_1,\ldots,Y_b$. Any two sets $X_i,Y_j$ should have a common element $p_{ab}$, and they are all distinct since $X_i$'s are disjoint aswell as $Y_j$'s. Therefore the ground set $S$ must contain at least $ab=\lfloor n^2/4\rfloor$ elements.

If I remember well, the edge set of any graph $G$ on $n$ vertices may be covered by a union of at most $f(n):=\lfloor n^2/4\rfloor$ cliques (cliques of size 2 and 3 should be enough), that implies $\delta(G)\leqslant \lfloor n^2/4\rfloor$. So this estimate for fixed $n$ is sharp.

The fact I am trying to remember should be provable by induction with removing a vertex with the minimal degree.

Indeed, let $v$ be a vertex of $G$ of minimal degree $d$, $N(v)$ be the set of neighbours of $v$. If $N(v)$ contains at least $d(v)-f(n)+f(n-1)$ disjoint edges, then the edges incident to $v$ may be covered by $f(n)-f(n-1)=\lfloor n/2\rfloor$ triangles and segments, and we may induct. If not, we have $d=\lfloor n/2\rfloor+k$ for some $k>0$, and $N(v)$ contains at most $k-1$ disjoint edges. Choose a maximal collection $\Omega$ of disjoint edges in $N(v)$. We have $k=d-\lfloor n/2\rfloor\leqslant n-1-\lfloor n/2\rfloor\leqslant \lfloor n/2\rfloor$, therefore the exist $w\in N(v)$ not covered by the edges from $\Omega$. This vertex $w$ may be joined with at most $2(k-1)$ vertices in $N(v)$, thus the degree of $w$ does not exceed $2(k-1)+n-d=n-2+k-\lfloor n/2\rfloor<\lfloor n/2\rfloor+k=d$, a contradiction.

Source Link
Fedor Petrov
  • 108.9k
  • 9
  • 264
  • 459

For finite graphs there exists a graph $G$ on $n$ vertices with $\delta(G)\geqslant \lfloor n^2/4\rfloor$. Namely, let $G$ be the disjoint union of two cliques $C_1,C_2$ on $a=\lceil n/2\rceil$ and $b=\lfloor n/2\rfloor$ vertices resp. The vertices of $C_1$ should correspond to disjoint sets $X_1,\ldots,X_a$, the vertices of $C_2$ to disjoint sets $Y_1,\ldots,Y_b$. Any two sets $X_i,Y_j$ should have a common element $p_{ab}$, and they are all distinct since $X_i$'s are disjoint aswell as $Y_j$'s. Therefore the ground set $S$ must contain at least $ab=\lfloor n^2/4\rfloor$ elements.

If I remember well, any edge set of the graph on $n$ vertices is a disjoint union of at most $\lfloor n^2/4\rfloor$ cliques (cliques of size 2 and 3 should be enough), that implies $\delta(G)\leqslant \lfloor n^2/4\rfloor$. So this estimate for fixed $n$ is sharp.