Simple Graphs

1 .Simple Graphs aka “Undirected Graphs” 3/19/12 1

2 .Types of Graphs Directed Graph Multi-Graph Simple Graph this week before spring break 3/19/12 2

3 .A simple graph: Definition: A simple graph G consists of a nonempty set, V , of vertices , and a set, E , of edges such that each edge has two distinct endpoints in V Write G = (V,E) 3/19/12 3

4 .vertices, V undirected edges, E A Simple Graph ::= { , } edge “adjacent ” 3/19/12 4

5 .A simple graph G: b d a e f c V ={ a,b,c,d,e,f } E ={{ a,d },{ a,e },{ b,c },{ b,e }, { b,f },{ c,f },{ d,f },{ e,f }} picture of G 3/19/12 5

6 .degree of a vertex is # of incident edges Vertex degree deg( ) = 2 3/19/12 6

7 .Vertex degree deg( ) = 4 degree of a vertex is # of incident edges 3/19/12 7

8 .Possible Graph? orphaned edge Is there a graph with vertex degrees 2,2,1? NO! 2 2 1 Im possible Graph ? 3/19/12 8

9 .sum of degrees is twice # edges Handshaking Lemma Proof : Each edge contributes 2 to the sum on the right 3/19/12 9

10 .Handshaking Lemma sum of degrees is twice # edges 2+2+1 = odd, so impossible 3/19/12 10

11 .Sex in America: Men more Promiscuous? Study claims: Men average many more partners than women. Graph theory shows this is nonsense 3/19/12 11 http://drjengunter.wordpress.com/2011/12 /03/how-many-sex-partners-do-people-really-have/

12 .M partners F Sex Partner Graph 3/19/12 12

13 .Counting pairs of partners divide by both sides by |M| 3/19/12 13

14 .Averages differ solely by ratio of females to males . No big difference Nothing to do with promiscuity Average number of partners 1.035 3/19/12 14

15 .Some Special Graphs Complete graph K n : A graph with n vertices including all possible edges K 5 : 3/19/12 15

16 .Bipartite Graph Graph in which vertices fall into two disjoint subsets and all edges have one endpoint in each 3/19/12 16

17 .Isomorphic Graphs Graphs (V,E) and (V’,E’) such that there is a bijection f : V→V’ that preserves edges: { v,w}∈E iff { f(v),f( w )}∈ E ’ Any two complete graphs of the same size are isomorphic 3/19/12 17 1 2 b d a e f c 3 4 5 6 a 2 b 4 c 6 d 3 e 1 f 5

18 .Finis 3/19/12 18