Conjecture about chordal graphs

115 Views Asked by At

I came up with the following conjecture: Let $G$ be a planar, biconnected chordal graph. Then there always exists a pair of adjacent vertices that have the same degree.

Can someone find a counter example?

1

There are 1 best solutions below

3
On

Start from a clique on vertices $\{t,u,v,w\}$ and add the following vertices:

  1. $x$ adjacent to $u$ and $w$;
  2. $y$ adjacent to $v$ and $w$;
  3. $z$ adjacent to $v$ and $w$.

This is chordal because we start with a chordal graph ($K_4$) and added new vertices whose neighborhoods are cliques in the previous graph.

It is biconnected because we started from a biconnected graph ($K_4$) and added new vertices with at least $2$ neighbors every time.

It is planar: it's a subgraph of this planar graph.

The degrees of $t,u,v,w,x,y,z$ are $3,4,5,6,2,2,2$, and none of $x,y,z$ are adjacent to each other.