An essential vertex in a graph is a vertex that is included in every possible maximum matching in the graph. My question is, is there anyway of constructing a connected graph that does NOT have an essential vertex?
Any help would be appreciated.
An essential vertex in a graph is a vertex that is included in every possible maximum matching in the graph. My question is, is there anyway of constructing a connected graph that does NOT have an essential vertex?
Any help would be appreciated.
Any odd cycle graph (eg. $C_7$) has no essential vertices as defined here. A maximum matching of $C_{2n+1}$ has $n$ edges, and any vertex can be the omitted one.