Est-ce que deux arbres couvrant un graphe simple ont toujours des bords communs?

J'ai essayé quelques cas et j'ai trouvé que deux arbres couvrant un graphique simple avaient des bords communs. Je veux dire que je n'ai pas trouvé de contre-exemple jusqu'à présent. Mais je n'ai pas pu prouver ou réfuter cela non plus. Comment prouver ou infirmer cette conjecture?

Non, considérons le graphique complet $K_4$ :

Il a les arbres s'étendant aux bords disjoints suivants:

Pour les lecteurs les plus intéressés, il existe des recherches sur la décomposition du graphique en arbres couvrant les bords disjoints .

$n$$k$

$K_{4k+2}$${2k+1}$

$K_{2n}$

Vous pouvez rechercher plus. Par exemple, une recherche Google pour la décomposition du graphique en plusieurs arbres .

$K_4$

Non, ce n'est pas vrai que deux arbres couvrant un graphe ont des bords communs.

Considérez le graphique de roue:

Vous pouvez créer un arbre couvrant avec des bords "à l'intérieur" de la boucle et un autre à partir de la boucle extérieure.

$K_n$$n\geq4$

$2$

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

$2$

1. $2$$2$
2. Y a-t-il un graphique autre que roue ou roue comme sous-graphique ayant des arbres s'étendant avec des bords disjoints?

$K_{2k}$

$$G_1 = \{ (v_{2i},v_{2i+1} ),(v_{2i},v_{2i+2}),\dots,(v_{2k-2},v_{2k-1})\},$$

$$G_2 = \{ (v_{2i+1},v_{2i+2}),(v_{2i},v_{2i}),\dots(v_{2(k-1)},v_{2(k-1)})\}$$

$0\leq i < k$

$n$$n+1$

Si le graphique a un pont (c'est-à-dire un bord dont la suppression déconnecte le graphique), ce bord doit appartenir à chaque arbre couvrant. Intuitivement, un pont est le seul bord reliant ses deux extrémités et appartient donc nécessairement à chaque sous-graphe connecté.

En revanche, si une arête du graphe appartient à un cycle, alors il existe un arbre couvrant ne contenant pas cette arête.

Donc, si chaque bord d'un graphe appartient à un cycle, alors aucun bord n'est commun à tous les arbres s'étendant (c'est-à-dire que l'intersection des ensembles d'arêtes des arbres s'étendant est l'ensemble vide).