Skip to main content
added 106 characters in body
Source Link
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

This holds if and only if $M$ has at most one connected component which contains a circuit. Clearly, the intersection graph of circuits is disconnected if $M$ has two connected components which each contain a circuit. For the other direction, suppose that $M$ has at most one connected component $N$ which contains a circuit. Let If $M$ has at most one circuit, then clearly the intersection graph of circuits is connected. Otherwise, let $C_1$ and $C_2$ be distinct circuits of $M$. Note that $C_1$ and $C_2$ are circuits of $N$. Choose $e \in C_1$ and $f \in C_2$. Since $N$ is connected, there is a circuit $C_3$ of $N$ such that $\{e,f\} \subseteq C_3$. Thus, there is path of length $2$ between $C_1$ and $C_2$ in the intersection graph of circuits.

This holds if and only if $M$ has at most one connected component which contains a circuit. Clearly, the intersection graph of circuits is disconnected if $M$ has two connected components which each contain a circuit. For the other direction, suppose that $M$ has at most one connected component $N$ which contains a circuit. Let $C_1$ and $C_2$ be distinct circuits of $M$. Note that $C_1$ and $C_2$ are circuits of $N$. Choose $e \in C_1$ and $f \in C_2$. Since $N$ is connected, there is a circuit $C_3$ of $N$ such that $\{e,f\} \subseteq C_3$. Thus, there is path of length $2$ between $C_1$ and $C_2$ in the intersection graph of circuits.

This holds if and only if $M$ has at most one connected component which contains a circuit. Clearly, the intersection graph of circuits is disconnected if $M$ has two connected components which each contain a circuit. For the other direction, suppose that $M$ has at most one connected component $N$ which contains a circuit. If $M$ has at most one circuit, then clearly the intersection graph of circuits is connected. Otherwise, let $C_1$ and $C_2$ be distinct circuits of $M$. Note that $C_1$ and $C_2$ are circuits of $N$. Choose $e \in C_1$ and $f \in C_2$. Since $N$ is connected, there is a circuit $C_3$ of $N$ such that $\{e,f\} \subseteq C_3$. Thus, there is path of length $2$ between $C_1$ and $C_2$ in the intersection graph of circuits.

added 12 characters in body
Source Link
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

This holds if and only if $M$ has at most one connected component which contains a circuit. Clearly, the intersection graph of circuits is disconnected if $M$ has two connected components which each contain a circuit. For the other direction, suppose that $M$ has at most one connected component $N$ which contains a circuit. Let $C_1$ and $C_2$ be distinct circuits of $M$. Note that $C_1$ and $C_2$ are circuits of $N$. Choose $e \in C_1$ and $f \in C_2$. Since $N$ is connected, there is a circuit $C_3$ of $N$ such that $\{e,f\} \subseteq C_3$. Thus, there is path of length $2$ in the intersection graph between $C_1$ and $C_2$ in the intersection graph of circuits.

This holds if and only if $M$ has at most one connected component which contains a circuit. Clearly, the intersection graph is disconnected if $M$ has two connected components which each contain a circuit. For the other direction, suppose that $M$ has at most one connected component $N$ which contains a circuit. Let $C_1$ and $C_2$ be distinct circuits of $M$. Note that $C_1$ and $C_2$ are circuits of $N$. Choose $e \in C_1$ and $f \in C_2$. Since $N$ is connected, there is a circuit $C_3$ of $N$ such that $\{e,f\} \subseteq C_3$. Thus, there is path of length $2$ in the intersection graph between $C_1$ and $C_2$.

This holds if and only if $M$ has at most one connected component which contains a circuit. Clearly, the intersection graph of circuits is disconnected if $M$ has two connected components which each contain a circuit. For the other direction, suppose that $M$ has at most one connected component $N$ which contains a circuit. Let $C_1$ and $C_2$ be distinct circuits of $M$. Note that $C_1$ and $C_2$ are circuits of $N$. Choose $e \in C_1$ and $f \in C_2$. Since $N$ is connected, there is a circuit $C_3$ of $N$ such that $\{e,f\} \subseteq C_3$. Thus, there is path of length $2$ between $C_1$ and $C_2$ in the intersection graph of circuits.

Source Link
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

This holds if and only if $M$ has at most one connected component which contains a circuit. Clearly, the intersection graph is disconnected if $M$ has two connected components which each contain a circuit. For the other direction, suppose that $M$ has at most one connected component $N$ which contains a circuit. Let $C_1$ and $C_2$ be distinct circuits of $M$. Note that $C_1$ and $C_2$ are circuits of $N$. Choose $e \in C_1$ and $f \in C_2$. Since $N$ is connected, there is a circuit $C_3$ of $N$ such that $\{e,f\} \subseteq C_3$. Thus, there is path of length $2$ in the intersection graph between $C_1$ and $C_2$.