Grafos - definições

Suponha por absurdo que todo vértice tem grau maior do que $1$. Considere o maior caminho simples $C = \{v_1, v_2,\dots, v_k\}$, onde $v_i$ está conectado a $v_{i+1}$ para todo $1 \leq i \leq k-1$. Como o grau de $v_1$ é maior do que $1$, existe um vértice $v\neq v_i \forall 1 \leq i \leq k$ vizinho de $v_1$ (por quê?) e, portanto, $C' = \{v, v_1, v_2, \dots, v_k\}$ é um caminho simples maior do que $C$, absurdo.

Caso 1. $G$ é conexo e não tem ciclos.

Provaremos por indução em $n$. Caso base: $n = 1$: claramente possui $1-1=0$ arestas. Suponha agora que todo grafo conexo e acíclico com $n-1$ vértices possui $n-2$ arestas. Seja $v$ uma folha de $G$. Por hipótese de indução, o subgrafo $G - \{v\}$ de $G$ possui $n-2$ arestas. Como $v$ tem grau $1$, $G$ tem $n-1$ arestas.

Caso 2. $G$ não tem ciclos e tem $n-1$ arestas.

Sejam $x_1, x_2, \dots, x_k$ a quantidade de vértices em cada componente conexa de $G$. Como cada componente conexa é uma árvore, temos que a quantidade de arestas de $G$ é $\sum_{i=1}^k {(x_i - 1)} = n-1$, mas $\sum_{i=0}^k x_i = n \implies k = 1 \implies G$ é conexo.

Caso 3: $G$ é conexo e tem $n-1$ arestas.

Suponha por absurdo que $G$ tem ciclos. Note que, ao remover uma aresta de um ciclo, o grafo continua conexo e o ciclo desaparece. Portanto se $G$ tem $k$ ciclos, podemos remover $k$ arestas e obter uma árvore com $n$ vértices, ou seja, $n-1-k=n-1 \iff k=0$, absurdo.

Sabemos que cada aresta em $G$ conecta um vértice em $X$ a outro em $Y$. Vamos contar a quantidade de elementos do conjunto $\{(v, a)|v\in X,a\in A$, em que o vértice $v$ é uma das extremidades da aresta $a$, de duas formas diferentes:

1) Para cada vértice $v$ em $X$ é uma das extremidades de exatamente $\deg(v)$ arestas em $A \Rightarrow$ Cada vértice $v$ em $X$ está em exatamente $\deg(v)$ pares distintos com a nossa propriedade desejada e cada par com a nossa propriedade desejada contém exatamente um vértice $v$ em $x$. Logo, há exatamente $\sum_{v\in X} \deg(v)$ tais pares.

2) Por outro lado, temos que cada aresta $a\in A$ possui exatamente uma extremidade $v$ em $X$. Daí, cada aresta em $A$, está em exatamente $1$ par $(v,a)$ com a nossa propriedade desejada e cada par com a nossa propriedade desejada contém uma aresta em $A$. Assim, há exatamente $|A|$ tais pares.

Desta forma, $\sum_{v\in X} \deg(v)=|A|$. Analogamente, contando a quantidade de pares $(v',a)$, em que o vértice $v'\in Y$ é uma das extremidades da aresta $a$, podemos concluir que $\sum_{v'\in Y} \deg(v')=|A|$.

Portanto, $\sum_{v\in X} \deg(v)=\sum_{v'\in Y} \deg(v')=|A|$.

(Ida) Se $G$ é bipartido, então ele não possui nenhum ciclo de tamanho ímpar.

Prova: Primeiramente, suponha por absurdo que há um ciclo ímpar no grafo bipartido $G$, digamos $C=(v_1,v_2,...,v_{2k+1},v_1)$, Assuma, sem perda de generalidade, que $v_1$ está no grupo $1$. Como $v_2$ é adjacente a $v_1$, eles devem ser de grupos diferentes $\Rightarrow v_2$ está no grupo $2$. De maneira similar, $v_3$ é adjacente a $v_2\Rightarrow v_3$ está no grupo $1$. Seguindo este raciocínio, teremos $v_{2i+1}$ no grupo $1$ e $v_{2i+2}$ no grupo $2$, para todo $i=0,1,2,...,k$. Isso implica que $v_{2k+1}$ e $v_1$ são dois vértices adjacentes que se encontram no mesmo grupo (Grupo 1), absurdo! Logo, não há ciclos ímpares em $G$.

(Volta) Se $G$ não possui ciclos de tamanho ímpar, então ele é bipartido.

Prova: Suponha que todos os ciclos de $G$ têm tamanho par. Tome um vértice qualquer $v_0$. Para cada vértice $v$ na mesma componente conexa $C_0$ que $v_0$, defina a distância de $v$ a $v_0$, e denote por $d(v)$, como o tamanho do menor caminho de $v_0$ a $v$. Coloque todos os vértices de $C_0$ cuja distância a $v_0$ é par em um grupo e coloque todos os vértices restantes em outro grupo. Faça o mesmo para cada componente conexa de $G$ (usando os mesmos dois grupos para todas). Vamos provar que não há arestas conectando vértices da no mesmo grupo.

Se dois vértices adjacentes $v_1$ e $v_2$, s.p.g. pertencentes à componente conexa $C_0$, foram colocados no mesmo grupo, então há um ciclo ímpar em $G$. De fato, o caminho indo de $v_0$ a $v_1$ (com tamanho $d(v_1)$), depois pela aresta conectando $v_1$ e $v_2$, em seguida pelo caminho indo de $v_2$ a $v_0$ (com tamanho $d(v_2)$) constitui um ciclo $C'$ de tamanho $1+d(v_1)+d(v_2)$. Contudo, estamos assumindo que $v_1$ e $v_2$ foram colocados na mesma componente conexa, o que significa que $d(v_1)$ e $d(v_2)$ têm a mesma paridade $\Rightarrow d(v_1)+d(v_2)$ é par $\Rightarrow 1+d(v_1)+d(v_2)$ é ímpar $\Rightarrow C'$ é um ciclo de tamanho ímpar, absurdo.

Logo, conseguimos dividir os vértices de $G$ em dois grupos tais que não há dois vértices adjacentes no mesmo grupo $\Rightarrow G$ é bipartido.

Portanto, $G$ é bipartido se, e somente se, ele não possui ciclos de tamanho ímpar.

Tente montar um grafo bipartido em que um dos grupos representa os soldados e o outro representa as noites.

Considere um grafo bipartido $G=S\dot\cup N$, em que $S=\{A_1,A_2,...,A_s\}$ é o conjunto de todos os $s$ soldados do quartel e $N=\{B_1,B_2,$ é o conjunto de $n$ noites. Conectamos um soldado $A_i$ e uma noite $B_j$ por uma aresta se, e somente se, o soldado $A_i$ ficou de vigília na noite $B_j$.

Sabemos que, para cada par de soldados $A_i$ e $A_j$, há exatamente uma noite $B_k$ na qual eles ficaram juntos de vigília. Ademais, suponha que os soldados de vigília na noite $B_k$ são $A_{i_1},A_{i_2}$ e $A_{i_3}\Rightarrow$ Cada noite $B_k$ contém exatamente $3$ pares de soldados: ($A_{i_1},A_{i_2}$), ($A_{i_1},A_{i_3}$) e ($A_{i_2},A_{i_3}$). Daí, ${s\choose 2}$=#(noite, par de soldados juntos de vigília nessa noite)=$3n$.

Portanto, ${s\choose 2}=3n\Rightarrow n=\frac{s^2-s}{6}$.

Realize uma contagem dupla sobre os pares (face, aresta sobre a borda desta face). Após provar isso, junte a desigualdade com o fato de que $V-A+F=2$.

Note que uma face sempre possui pelo menos $3$ arestas e cada aresta é contada em exatamente duas faces. Logo, ao contarmos o número de pares descritos na dica:

1. Fixada a aresta (A formas) temos $2$ faces em que ela contabiliza

2. Fixada a face (F formas), temos $3$ arestas no mínimo em que ela contabiliza

Logo, $3F\leq 2A$. Plugando na fórmula de Euler: $3V -6 \geq A$. Como há $5$ vértices e $10$ arestas no $K_{5}$, chegamos num absurdo.

Para provar o teorema vamos aplicar indução na quantidade de vértices, suponha que a condição vale para um torneio de $n$ vértices, tome um torneio de $n+1$ vértices, ao retirar um deles, sabemos que existe um caminho passando por todos os outros, vamos olhar para esse caminho e para as arestas que ligam o vértice destacado aos outros

Se a aresta entre $v_1$ e $v_{n+1}$ sair do segundo, podemos pegar o caminho:

$v_{n+1}\to v_1\to v_2 \to ... \to v_n$

Logo supomos que $v_1$ aponta para $v_{n+1}$, analogamente dizemos que $v_2$ aponta para $v_{n+1}$ senão podemos pegar o caminho:

$v_1\to v_{n+1}\to v_2 \to ... \to v_n$

Porém se todas as arestas chegarem em $v_{n+1}$, sabemos em particular que $v_n$ aponta para $v_{n+1}$ e assim temos o caminho:

$v_1\to v_2 \to ... \to v_n\to v_{n+1}$

Logo, basta averiguar os casos iniciais e para $n=2$ é fácil ver que vale

Lema 1: Num grafo com uma quantidade ímpar de arestas podemos direcionar as arestas para que apenas um vértice tenha out-grau ímpar

Prova:  Vamos aplicar indução na quantidade de arestas, suponha que vale para todo grafo com no máximo $2n-1$ arestas e suponha verdadeiro o enunciado da questão tome um grafo com $2n+1$ arestas e escolha um vértice($v$) e retire uma aresta ligada a ele (ligada a $u$) se o que sobra é um grafo conexo, organize as arestas para $v$ e $u$ tenham out-grau par e faça a aresta $vu$ sair de $v$ assim $v$ é o único com out-grau ímpar, faça o mesmo se $u$ e $v$ acabarem em componentes conexas diferentes cada uma com uma quantidade par de arestas, caso contrário, é possível organizar por hipótese as arestas de tal forma que $u$ e $v$sejam os únicos com out-grau ímpar então basta que a aresta retirada saia $u$  e parta para $v$.

$\square$

Como a quantidade de arestas é par sabemos que existem ao menos 3 vértices e por ser conexo sabemos que existe um vértice com grau pelo menos 2. Vamos aplicar indução no número de arestas, assim, supomos que a condição vale para todo valor de arestas menor ou igual a $n$ tome um grafo de $2n+2$ arestas e escolha um vértice com grau pelo menos $2$($v$) retire ambas arestas (sejam elas ligadas aos vértices $v_1$ e $v_2$), assim você terá um grafo conexo com uma quantidade par de arestas ou um grafo não conexo com no máximo $3$ componentes conexas.

No primeiro caso, basta aplicar a condição para o grafo restante já que você tem uma quantidade par de arestas e recolocar as duas que foram retiradas ambas saindo de $v$ mantendo assim a paridade do out-grau dos vértices.

Para  o próximo temos que tomar cuidado com uma possível componente conexa com uma quantidade ímpar de arestas dessa forma, se houverem apenas componentes conexas com uma quantidade par de arestas, é possível organizar as arestas para $v$, $v_1$ e $v_2$ terem out-grau par então basta fazer as arestas retiradas saírem de $v$. Se houver uma componente conexa com ímpar arestas, sabemos que podemos direcionar as arestas de tal forma que dois dos vértices nomeados tenham out-grau ímpar, assim fazemos uma das arestas destacadas apontar para um vértice de out-grau par e agora temos dois de out-grau par e outro ímpar, para finalizar fazemos a outra aresta destacada sair do vértice de grau ímpar

$\square$

Vamos provar que o mínimo é $0$ por indução, suponha que vale para $2n-1$ equipes, tome um torneio com $2n-1$ equipes sem triângulos cíclicos, note que podemos adicionar um vértice que ganhou de todas equipes e outro que perdeu para todas dessa forma não adicionamos nenhum triângulo novo, já que para que haja um triângulo os vértices devem ter pelo menos uma aresta entrando e outra saindo, dessa forma, os vértices adicionados não poderam formar nenhum triângulo.

Veja que para $n=1$ temos o grafo abaixo, logo a indução está completa.

Para maximizar a quantidade de triângulos cíclicos($C_3$), vamos contar a quantidade de triângulos não cíclicos($C_3'$)  já que sabemos que:

• $C_3+C_3'=\binom{2n+1}{3}$

Pois a quantidade de triângulos cíclicos e não cíclicos compreendem todas as possibilidades de triângulos. Assim, note que qualquer triângulo não cíclico é do tipo da figura do item a), logo para contar quantos deles existem num torneio, basta pegar todos os vértices e escolher duas arestas saindo dele, logo:

$\sum\binom{g^-(v_i)}{2}=C_3'\iff$

$\iff \sum\frac{g^-(v_i)^2}{2}-\sum\frac{g^-(v_i)}{2}=C_3'\iff$

$\iff \sum\frac{g^-(v_i)^2}{2}-\frac{\binom{2n+1}{2}}{2}=C_3' \iff$

$\iff \sum (g^-(v_i)^2)=2C_3'+n(2n+1)$

Porém por $MQ \geq MA$, sabemos que:

$\sqrt{\frac{\sum (g^-(v_i)^2)}{2n+1}}\geq \frac{\sum g^-(v_i)}{2n+1}=\frac{\binom{2n+1}{2}}{2n+1}=n\iff$

$\iff \sum (g^-(v_i)^2)\geq n^2(2n+1)$

Logo:

$2C_3'+n(2n+1) \geq n^2(2n+1)\iff$

$C_3' \geq \frac{n(2n+1)(n-1)}{2}$

Finalmente, concluimos que:

$C_3=\binom{2n+1}{3} - C_3'\leq \binom{2n+1}{3}-\frac{n(2n+1)(n-1)}{2} \iff$

$\iff C_3\leq \frac{(2n+1)n(n+1)}{6}$

Logo, o máximo de triângulos cíclicos possíveis num torneio de $2n+1$ equipes é $\frac{(2n+1)n(n+1)}{6}$ ocorrendo quando saem e entram exatamente $n$ arestas de cada vértice(caso de igualdade da $MQ\geq MA$)