When learning definition of essential and inessential vertices, out of curiosity, I am looking for a graph which contains a path that only consists of essential/inessential vertices.
A vertex is essential iff removing this vertex will not change the size of any maximum matching. A vertex is inessential iff the opposite happens.
So far I only find one example which meets my condition:
- A cycle has only essential or inessential vertices so I will put "cycle" into my list.
Meanwhile, I would like to know if there is a graph which will never contain such a path that ONLY consists of essential/inessential vertices. For example, for a complete bipartite graph $K_(m, n)$ where $m < n$, such a path never exists.
Could you anyone interested in this question provide some examples? If you could tell me some graphs which contain or will never contain a path that consist of only essential/inessential paths, that will be great. Also, beside cycle, I would like to see some planar graphs which can meet my requirement.
Thank you in advance.