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

Assuming that $G$ is connected, we can get a characterization by looking at the block decomposition $B(G)$ of $G$ into 2-connected pieces. That is, we simply look at which vertices of $B(G)$ are $K_2$'s. The required characterization is:

$B(G)$ does not contain two adjacent vertices which are both Every vertex of $K_2$'s and no leaf$G$ is contained in a block of $B(G)$$G$ which is not a $K_2$.

Of course, this is the same answer as Harrison's, but it gives a more global view. Also, necessity and sufficiency are trivial.

Assuming that $G$ is connected, we can get a characterization by looking at the block decomposition $B(G)$ of $G$ into 2-connected pieces. That is, we simply look at which vertices of $B(G)$ are $K_2$'s. The required characterization is:

$B(G)$ does not contain two adjacent vertices which are both $K_2$'s and no leaf of $B(G)$ is a $K_2$.

Of course, this is the same answer as Harrison's, but it gives a more global view. Also, necessity and sufficiency are trivial.

Assuming that $G$ is connected, we can get a characterization by looking at the block decomposition $B(G)$ of $G$ into 2-connected pieces. That is, we simply look at which vertices of $B(G)$ are $K_2$'s. The required characterization is:

Every vertex of $G$ is contained in a block of $G$ which is not a $K_2$.

Of course, this is the same answer as Harrison's, but it gives a more global view. Also, necessity and sufficiency are trivial.

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

Assuming that $G$ is connected, we can get a characterization by looking at the block decomposition $B(G)$ of $G$ into 2-connected pieces. That is, we simply look at which vertices of $B(G)$ are $K_2$'s. The required characterization is:

$B(G)$ does not contain two adjacent vertices which are both $K_2$'s and no leaf of $B(G)$ is a $K_2$.

Of course, this is the same answer as Harrison's, but it gives a more global view. Also, necessity and sufficiency are trivial.