First Theorem of Graph Theory - Revision history

Admin: /* Notes */

2019-04-26T22:04:46Z

Notes

← Older revision		Revision as of 22:04, 26 April 2019
Line 3:		Line 3:
	The first theorem of graph theory states:		The first theorem of graph theory states:

	''Suppose a graph G has n vertices and a edges. Suppose the degrees of each of the N nodes are denoted <math>d_1, d_2, \dots, d_N<math>.''		''Suppose a graph G has n vertices and a edges. Suppose the degrees of each of the N nodes are denoted <math>d_1, d_2, \dots, d_N</math>.''

	''Then the following statement is true:''		''Then the following statement is true:''

Admin: /* Notes */

2019-04-26T22:04:31Z

Notes

← Older revision		Revision as of 22:04, 26 April 2019
Line 3:		Line 3:
	The first theorem of graph theory states:		The first theorem of graph theory states:

	''Suppose a graph G has n vertices and a edges. Suppose the degrees of each ~~graph~~ are denoted d1, d2, d3, .~~.., dn.~~ Then the following statement is true:''		''Suppose a graph G has n vertices and a edges. Suppose the degrees of each of the N nodes are denoted <math>d_1, d_2, \dots, d_N<math>.''

			''Then the following statement is true:''

	<math>		<math>

Admin: /* Links */

2019-04-26T22:00:09Z

Links

← Older revision		Revision as of 22:00, 26 April 2019
Line 27:		Line 27:
	==Links==		==Links==

	Course notes from Wayne Goddard at Clemson: https://people.cs.clemson.edu/~goddard/texts/discreteMath/~~13.pdf~~		Course notes from Wayne Goddard at Clemson: https://people.cs.clemson.edu/~goddard/texts/discreteMath/

	Also see: https://people.cs.clemson.edu/~goddard/		Also see: https://people.cs.clemson.edu/~goddard/

Admin: /* Notes */

2017-09-07T13:04:55Z

Notes

← Older revision		Revision as of 13:04, 7 September 2017
Line 17:		Line 17:
	This is a consequence of the equation given above: if a sum (sum of vertex degrees, left side of the equation) is even, there must be an even number of odd summands.		This is a consequence of the equation given above: if a sum (sum of vertex degrees, left side of the equation) is even, there must be an even number of odd summands.

	For a graph to be Eulerian, that is, for an [[~~Graph~~/Euler Tour]] to exist on the graph, the number of vertices with odd degree must be 0 or 2.		For a graph to be Eulerian, that is, for an [[Graphs/Euler Tour]] to exist on the graph, the number of vertices with odd degree must be 0 or 2.

	=Resources=		=Resources=

Admin: Created page with "=Notes= The first theorem of graph theory states: ''Suppose a graph G has n vertices and a edges. Suppose the degrees of each graph are denoted d1, d2, d3, ..., dn. Then the..."

2017-09-07T13:04:42Z

Created page with "=Notes= The first theorem of graph theory states: ''Suppose a graph G has n vertices and a edges. Suppose the degrees of each graph are denoted d1, d2, d3, ..., dn. Then the..."

New page

=Notes=

The first theorem of graph theory states:

''Suppose a graph G has n vertices and a edges. Suppose the degrees of each graph are denoted d1, d2, d3, ..., dn. Then the following statement is true:''

<math>
\sum_{i=0}^{n} d_i = 2a
</math>

The proof of this can be shown through the double counting argument. The left and right sides above both count the number of endpoints of edges. Summing up the degrees of each vertex counts up the number of ends of edges. Since each edge has two ends, we count each edge twice, and therefore the number of endpoints counted must be even.

A direct consequence of this is the following fact:

''In any graph, the number of vertices of odd degree must be even.''

This is a consequence of the equation given above: if a sum (sum of vertex degrees, left side of the equation) is even, there must be an even number of odd summands.

For a graph to be Eulerian, that is, for an [[Graph/Euler Tour]] to exist on the graph, the number of vertices with odd degree must be 0 or 2.

=Resources=

==Related Pages==

[[Graphs/Euler Tour]]

==Links==

Course notes from Wayne Goddard at Clemson: https://people.cs.clemson.edu/~goddard/texts/discreteMath/13.pdf

Also see: https://people.cs.clemson.edu/~goddard/

=Flags=

{{GraphsFlag}}