How to check if a directed graph is eulerian?
1) All vertices with nonzero degree belong to a single strongly connected component.
2) In degree is equal to the out degree for every vertex. Source: geeksforgeeks
Question: In the given two conditions, is the first one strict? I mean why is it really necessary for the graph to be "strongly" connected graph? What if the graph is just connected?
I learned that condition 1 can be replaced with weakly connected graph. Again, what if the graph is just connected instead of weakly connected? Will be glad to see some examples.
P.S: Consider condition 2 is always fulfilled in the above discussion. And by "just connected", I mean there exists a vertex in the graph from which all other vertices are reachable.
This is an interesting question. There is, to the best of my knowledge, no standardized meaning of "connected" in the context of a directed graph. The two general notions of connectivity in a directed graph are
Your version of the directed graph being "just connected" is slightly different than these definitions, but it's related to strong connectivity. Any directed graph can have its nodes partitioned into strongly connected components (SCCs), groups of nodes that can all reach one another. Those strongly connected components form a DAG, where each strongly connected component is a node and there's an edge from one SCC to another if one of the nodes in the first SCC has an edge to a node in the second SCC.
Your definition of the graph being "just connected" could then be pinned down like this:
Notice that "just connected" implies weakly connected, but not the other way around.
It turns out that, in this case, if you have a graph where each node's indegree happens to equal its outdegree, then if the graph is "just connected," then it has an Euler circuit. If your graph is "just connected," then it's weakly connected. Then, we're going to claim that any weakly connected graph with indegrees equal to outdegrees must be strongly connected as well. To see this, pick any SCC in the DAG of SCCs with no incoming edges. Any edge entering any of the nodes in this SCC must come from within that SCC. As a result, if we went through each node in the SCC and added up the number of edges leaving that node, that total would match the number of incoming edges into each node in the SCC. But then, since the sum of indegrees of nodes equals the sum of outdegrees of the nodes, there can't then be any edges starting within this SCC and ending in another, since all edges are accounted for. Therefore, this SCC has no edges leaving it.
We've just shown that any source SCC must have no edges to any other SCCs. And since there is some node in some source SCC that can reach every node, this means that there are no other SCCs in the graph, so the graph has just one SCC and is therefore strongly connected.