graph theory

Question 1

bipartite graph

Answer 1

graph whose vertices can be divided into 2 disjoint sets in which all edges contain one vertex from each set

Question 2

matching

Answer 2

set of edges without common vertices

Question 3

complete matching

Answer 3

every vertex incident to some edge in the matching

Question 4

path

Answer 4

sequence of vertices where all vertices are adjacent and no vertex repeats

Question 5

circuit, cycle

Answer 5

sequence of adjacent vertices, first and last adjacent

Question 6

connectivity

Answer 6

if for all pairs there exists a path

Question 7

ismorphism

Answer 7

bijection function such that v1,v2 are adjecent if f(v1) is adjacent to f(v2)

Question 8

graph complement

Answer 8

graph drawn on the same set of vertices but a complementary set of edges

Question 9

walk

Answer 9

sequence of edges which joins a sequence of vertices

Question 10

trail

Answer 10

walk in which all edges are distinct

Question 11

path graph

Answer 11

on n vertices, can be expressed as a single path

Question 12

circuit graph

Answer 12

on n vertice, can be expressed as a single circuit

Question 13

complete graph

Answer 13

on n vertice, all pairs of vertices are complete

Question 14

planar graphs

Answer 14

if it can be drawn in a plane without edges crossing

Question 15

eular cycle

Answer 15

cycle ( with no repeated edges ) that transverses every edge ( has to have even degree )

Question 16

eular trail

Answer 16

trail ( no repeated edges ) that traverses every edge, 2 vertices have odd degree

Question 17

hamilton circuit

Answer 17

circuit ( no repeated vertices ) that passes through every vertex ( don’t have to hit every edge )

Question 18

graph coloring

Answer 18

assignment of colors to vertices such that no pair of adjacent vertices are of the same color

Question 19

chromatic number

Answer 19

fewest number of colors that can be used to make a valid coloring

Question 20

star graph

Answer 20

connected graph where all vertices have 1 degree and center vertex has degree n-1

Question 21

wheel graph

Answer 21

circuit with a center vertex that connects to every vertex in circuit

Question 22

dual graph

Answer 22

graph in which regions are mapped to vertices and adjacency is preserved

Question 23

chromatic polynomial

Answer 23

number of ways to color G with k colors

Question 24

tree

Answer 24

undirected graph with no circuits; a graph which contains a unique path from root to any other vertex

Question 25

rooted tree

Answer 25

directed tree with a unique root ( exists a path from the root to every other vertex )

Question 26

level number

Answer 26

length of the path from the root

Question 27

binary tree

Answer 27

each parent has exactly three children

Question 28

ternary tree

Answer 28

each parent has exactly three children

Question 29

m-ary tree

Answer 29

each interval vertex has exactly m children

Question 30

balanced tree

Answer 30

a tree of height h is balanced if all of the leaves are at level h or h-1