Graph theory

Question 1

adjacent

Answer 1

two vertices connected by and edge

Question 2

incident

Answer 2

the edge e=(y,v) is incident with u and v

Question 3

handshaking theorem undirected

Answer 3

2E = sum(degrees of v)

Question 4

handshaking theorem Directed graphs

Answer 4

E= degree outv = degree inv

Question 5

chromatic number of Kn

Answer 5

complete n

Question 6

chromatic number of Cn

Answer 6

circle 3 odd, 2 even

Question 7

Wn chromatic

Answer 7

wheel 3 odd 4 even

Question 8

Sn

Answer 8

star graphs 2

Question 9

Bipartite

Answer 9

iff vertices of G can be colored by 2 or fewer colors

iff every circuit has even length

Question 10

Euler circuit

Answer 10

a simple circuit containing every edge of G

Question 11

Euler Path

Answer 11

a simple path containing every edge of G

Question 12

how to tell if it has a Euler circuit

Answer 12

Every vertex must have an even degree

Question 13

how to tell if it has a Euler path

Answer 13

has exactly 2 vertices of odd degree rest must be even

Question 14

Hamiltonian circuit

Answer 14

a circuit covering each vertex exactly once

Question 15

Planar

Answer 15

can be drawn in the plane without crossing edges

Question 16

eulers formula for connected planar graphs

Answer 16

V-E+R =2

Question 17

Edge bound for connected planar simple graphs

Answer 17

E<=3V-6

Question 18

Edge bound for connected planar simple graphs without triangles

Answer 18

E<=2V-4

Question 19

Kurtowskis theorem

Answer 19

G is nonplanar iff it contains a subgraph K5 or K3,3 cant bge greater than 5 or 3

Question 20

4 color theorem

Answer 20

for planar graphs the chromaic number cant be more than 4

Question 21

height of a tree

Answer 21

counted by edges for discrete

Question 22

spanning tree

Answer 22

is a sugraph of G that contains every vertex of G

Question 23

how to tell if a simple graph is connected

Answer 23

a simple graph is connected iff it has a spanning tree.

spanning rees have n-1 edges wehre n is averitce

Question 24

minimum spanning tree

Answer 24

for weighted graphs, a tree with the minimum weight

Question 25

Prims algorithm

Answer 25

Start with edge of minimum weight. pick next largest that is incident to the edge you have, get all the vertices wtihout making a circuit

Question 26

Krustals algorithm

Answer 26

CHoose the edges that are minimum. keep moving up in weight until all vertices are connected with no circuits

Question 27

Reflexive

Answer 27

loops at every vertex

1s on the main diagonal

Question 28

symmetric

Answer 28

No single edges between vertices

symmetric about main diagonal

Question 29

transitive

Answer 29

any directed path of length 2 must have a connecting path

Question 30

equivalence.

Answer 30

reflexive, transitive, and symmetric