Duas árvores de um gráfico simples sempre têm algumas arestas em comum?

Tentei alguns casos e descobri que duas árvores abrangidas de um gráfico simples têm algumas arestas comuns. Quero dizer, não consegui encontrar nenhum exemplo contrário até agora. Mas também não pude provar ou refutar isso. Como provar ou refutar essa conjectura?

Não, considere o gráfico completo :$K_4$

Possui as seguintes árvores de abrangência distintas:

Para os leitores mais interessados, há algumas pesquisas sobre a decomposição de gráfico em árvores de abrangência distintas .

Por exemplo, os artigos clássicos Sobre o Problema de Decompor um Gráfico em Fatores Conectados$n$ por WT Tutte e árvores disjuntas de arestas de gráficos finitos de C. St.JA Nash-Williams fornece uma caracterização de gráficos que contêm arestas disjuntas aos pares abrangendo árvores.$k$

Por exemplo, as decomposições bicíclicas em papel de gráficos completos em árvores abrangidas por Dalibor Froncek mostram como decompor gráficos completos em árvores abrangidas isomórficas .$K_{4k+2}$${2k+1}$

Por exemplo, o artigo Fatorações de gráficos completos em árvores de abrangência com todos os graus máximos possíveis de Petr Kovář e Michael Kubesa mostra como fatorar em árvores de abrangência com um determinado grau máximo.$K_{2n}$

Você pode procurar por mais. Por exemplo, uma pesquisa no Google por decomposição de gráfico em árvores de abrangência .

EDIT: Isso está incorreto, como apontado nos comentários. Como a outra resposta diz, uma árvore geradora de $K_4$ pode ser feito sem partilha bordas.

Não, não é verdade que duas árvores abrangidas de um gráfico tenham arestas em comum.

Considere o gráfico da roda:

Você pode fazer uma árvore de abrangência com arestas "dentro" do loop e outra a partir do loop externo.

$K_n$$n\geq4$

$2$

$K_n$$n\geq4$$n\geq4$$2$

$2$

1. $2$$2$
2. Existe algum gráfico que não seja roda ou roda como seu subgrafo tendo árvores de abas com arestas desconexas?

$K_{2k}$

$0\leq i < k$

$n$$n+1$

Se o gráfico tiver uma ponte (ou seja, uma aresta cuja remoção desconecta o gráfico), essa aresta deve pertencer a todas as árvores de abrangência. Intuitivamente, uma ponte é a única aresta conectando seus dois pontos finais e, portanto, necessariamente pertence a todos os subgráficos conectados.

Por outro lado, se uma aresta do gráfico pertencer a um ciclo, existe uma árvore de abrangência que não contém essa aresta.

Portanto, se todas as arestas de um gráfico pertencem a um ciclo, nenhuma aresta é comum a todas as árvores estendidas (ou seja, a interseção dos conjuntos de arestas das árvores estendidas é o conjunto vazio).