1.5 ATheorem from Discrete Mathematics 5 1.4 Eulerian Graphs and Digraphs A circuit in a nontrivial connected graph G that contains every edge of G (necessarily exactly once)is an Eulerian circuit in a graph.A connected graph G is Eulerian if G contains an Eulerian circuit.The following characterization of Eulerian graphs is attributed to Leonhard Euler. Theorem 1.4.1 ([31)).A nontrivial connected graph G is Eulerian if and only if every vertex ofG has even degree These concepts dealing with raphs as well.Ar Eulerian ci rcir mn a con at contains every arc of D.A connected digraph that contains an Eulerian circuit is an Euleriar digraph.As with the characterization of Eulerian graphs in Theorem 1.4.1,the characterization of Eulerian digraphs stated next is given in terms of the digraph analogues of'degrees'.The ourdegree odv of a vertex v in a digraph D is the number of arcs incident with and directed away from v,while the indegree idv ofis the number of ares incident with and directed towards. For example,since odv=idv for every vertex v of the digraph D of Fig.1.1,it is Eulerian and(v1.v2.v3.v7.v6.v2.v4.v6.vs,v.v)is an Eulerian circuit of D. 1.5 A Theorem from Discrete Mathematics t ome basic factsn mthemihogh on,there is one result that we wil encounter so c ten that it valuable to state here at the beginning.This result deals with combinations with repetition. Theorem 1.5.1.Let A be a multiset containing t different kinds of elements,where there are at least r elements of each kind.The number of different selections of r elements from Ais(t-l） Fig.1.1 An Eulerian digraph D 1.5 A Theorem from Discrete Mathematics 5 1.4 Eulerian Graphs and Digraphs A circuit in a nontrivial connected graph G that contains every edge of G (necessarily exactly once) is an Eulerian circuit in a graph. A connected graph G is Eulerian if G contains an Eulerian circuit. The following characterization of Eulerian graphs is attributed to Leonhard Euler. Theorem 1.4.1 ([31]). A nontrivial connected graph G is Eulerian if and only if every vertex of G has even degree. These concepts dealing with graphs have analogues for digraphs as well. An Eulerian circuit in a connected digraph D is a directed circuit that contains every arc of D. A connected digraph that contains an Eulerian circuit is an Eulerian digraph. As with the characterization of Eulerian graphs in Theorem 1.4.1, the characterization of Eulerian digraphs stated next is given in terms of the digraph analogues of ‘degrees’. The outdegree od v of a vertex v in a digraph D is the number of arcs incident with and directed away from v, while the indegree id v of v is the number of arcs incident with and directed towards v. Theorem 1.4.2. Let D be a nontrivial connected digraph. Then D is Eulerian if and only if od v D id v for every vertex v of D. For example, since od v D id v for every vertex v of the digraph D of Fig. 1.1, it is Eulerian and .v1; v2; v3; v7; v6; v2; v4; v6; v5; v4; v1/ is an Eulerian circuit of D. 1.5 A Theorem from Discrete Mathematics While we will use some basic facts and results from discrete mathematics through￾out our discussion, there is one result that we will encounter so often that it is valuable to state here at the beginning. This result deals with combinations with repetition. Theorem 1.5.1. Let A be a multiset containing ` different kinds of elements, where there are at least r elements of each kind. The number of different selections of r elements from A is rC`1 r  . Fig. 1.1 An Eulerian digraph D ... .. ........ .................. ... .. ........ .................. ... .. ........ .................. ... .. ........ .................. ... .. ........ .................. ... .. ........ .................. ... .. ........ .................. ................................................. .................................................. ................................................ .................................................. .......... . . .. .. ........... . ......... ......... . . . . .. .. ........... ........ .......... . . ......................... .......... . . ......................... ... ... ... ... .......... ... ... ... .... ................................... ... .......... ....... ....... ...... ...... ............. .... . . . . . . .. .. .... ....... ... ... .......... .. .. .. .................... ............ ................... .. .. .. . v3 v4 v1 v2 v5 v6 v7 D :