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?
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?
Copyright © 2021 JogjaFile Inc.
Start from a clique on vertices $\{t,u,v,w\}$ and add the following vertices:
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.