L={(G,v)G is an undirected graph containing at least one circle which itself contains vertex v}
R={(G,v)G is an undirected graph containing at least one circle which itself contains vertex v, and at least one circle which itself does not contain vertex v}
Take the 2minute tour
×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.



In fact, since Reingold proved that STCONN is in L these languages are also in L. The proof for the first is the following. For every u neighbor of v, delete the uv edge and check whether u and v are connected in the resulting graph. If yes, then there is a cycle. If the answer is no for all u, then there is no cycle containing v. The proof of the second is similar, first check for a cycle containg v, then consider all the edges of v deleted and check whether there is a cycle in the remaining graph, e.g. as before for every pair of vertices. 

