combinatorics

Question 1

order of a graph

Answer 1

n, number of vertices

Question 2

size of a graph

Answer 2

m, number of edges

Question 3

trivial graph

Answer 3

order 1

Question 4

empty graph

Answer 4

size 0

Question 5

complete graph

Answer 5

every pair of vertices is connected

Question 6

degree of a vertex

Answer 6

the number of vertices connected to vertex

Question 7

delta G

Answer 7

max degree of G

Question 8

S(G)

Answer 8

min degree of g

Question 9

if G is a graph of size m, the sum of the degrees of v =

Answer 9

2m

Question 10

any graph has a ___ number of vertices with odd degrees

Answer 10

even

Question 11

isomorphic

Answer 11

if uv are adjacent in G, then they’re adjacent in H

Question 12

bipartite graph

Answer 12

if vertices can be partitioned into two sets, and if uv is an edge, u and v are not in the same set

Question 13

size of a bipartite graph of order n is

Answer 13

at most ceil(n/2)*floor(n/2)

Question 14

the size of a bipartite graph is <=

Answer 14

ceil(n^2/4)

Question 15

size of a bipartite graph =

Answer 15

ceil(n^2/4) iff n is even

Question 16

No bipartite graph contains a

Answer 16

triangle

Question 17

if size of a graph is > ceil(n^2/4)

Answer 17

G has c3 as a subgraph

Question 18

a degree sequence is not a sequence of a graph when

Answer 18

sum of degrees is odd, or if one of the degrees is greater than the number of vertices of the graph

Question 19

erdos gollci theorem

Answer 19

a degree sequence is graphical iff the sum is even and the sum from 1 to k [degrees] <= k(k+1) + sum k+1 to n [min(k, d)]

Question 20

u-v walk

Answer 20

sequence of vertices beginning with u and ending with v

Question 21

u-v trail

Answer 21

walk where no edge is traversed more than once

Question 22

u-v path

Answer 22

walk where no vertex is visited more than once

Question 23

circuit

Answer 23

closed trail of length 3 or more

Question 24

adjacency matrix of a graph

Answer 24

nxn matrix where aij is 1 if vi,vj is an edge, 0 if not

Question 25

incidence matrix of a graph

Answer 25

nxm matrix where bij is 1 if v incident to an edge, 0 otherwise

Question 26

d(u,v)

Answer 26

min length of a u-v walk

Question 27

eccentricity of a vertex e(u)

Answer 27

max distance u is from another vertex

Question 28

diameter of graph

Answer 28

max eccentricity

Question 29

radius of graph

Answer 29

min eccentricity

Question 30

central vertex u

Answer 30

if eccentricity(u) = diameter(G)

Question 31

center of G

Answer 31

subgraph created by all the central vertices

Question 32

periphery of G

Answer 32

subgraph created by the not central vertices

Question 33

rad G <= ? <= ?

Answer 33

diam(G), 2rad(G)

Question 34

if T is a tree of order n, size m, then m =

Answer 34

n-1

Question 35

a degree sequence of a tree if

Answer 35

sum of degrees = 2n-2

Question 36

a set of vertices u in a graph is independent if

Answer 36

no edges between vertices of u

Question 37

independence number of G

Answer 37

max number of vertices in an independent set

Question 38

chromatic number X(G)

Answer 38

minimum amount of colors needed to give a proper coloring

Question 39

clique number W(G)

Answer 39

order a largest complete subgraph

Question 40

X(G) () W(G)

Answer 40

>=

Question 41

Lames theorem

Answer 41

Iterations of Euclidean algorithm < lnb/lna + 1