Graph theory

Question 1

What is a simple graph?

Answer 1

A simple graph G is a pair of sets G(V,E) such that each element E is a 2 element subset of V.

Question 2

What is the n-cube graph? (Qn)

Answer 2

It is a graph formed from the vertices and edges of an n dimensional hype cube.

Question 3

What is the hand shaking lemma?

Answer 3

For any graph, the sum of the degrees of the vertices is equal to twice the number of edges.

Question 4

What is the definition of isomorphism

Answer 4

Two simple graphs are isomorphic if there exists a bijection which preserves adjacency.

Question 5

What is the compliment of G?

Answer 5

It is the graph which has all the other possible edges.

Question 6

What is a walk?

Answer 6

It is a sequence of vertices and edges with vi and ei not necessarily distinct. v1,e1,v2,…,vk-1,ek-1,vk

Question 7

What is the length of a walk?

Answer 7

k-1

Question 8

what is a closed walk?

Answer 8

A walk in which the first vertex is equal to the last.

Question 9

what is a trail?

Answer 9

A walk with no edges repeated

Question 10

what is a circuit?

Answer 10

A closed trail.

Question 11

what is a path?

Answer 11

A walk with no vertex repeated

Question 12

What is an n-cycle?

Answer 12

A cycle with n vertices and so n edges

Question 13

What is lemma 2.1

Answer 13

If a graph G has a walk from vertex v to vertex w, v≠w then G has a path from v to w.

Question 14

What is lemma 2.2

Answer 14

if every vertex in a finite graph has degree >1 then G contains a cycle

Question 15

what is a connected graph>

Answer 15

One in which given a v,w in V, there is a path from v to w.

Question 16

What is an unconnected graph

Answer 16

One with two or more unconnected components

Question 17

What is a bridge

Answer 17

An edge whose removal will increase the number of connected components.

Question 18

What is a euler circuit

Answer 18

A circuit using each edge exactly once.

Question 19

What is a graph with a euler circuit called

Answer 19

Eulerian

Question 20

What is euler’s theorem

Answer 20

Let G be a finite connected graph. Then G has a euler circuit if and only if all vertices are of even degree.

Question 21

What is lemma 2.5

Answer 21

If G is finite connected with all vertices of even degree, then G is a finite union of edge disjoint cycles.

Question 22

What is a bipartite graph

Answer 22

Suppose V=V1⋃V1 and V1∩V2=∅ and every edge has one end in V1 and one end in V2

Question 23

What is a planar graph

Answer 23

One which can be drawn in the plane so that no edges meet except at their end points.

Question 24

What is a face

Answer 24

They are the regions which a planar representation of a graph divides the graph into

Question 25

What is the boundary of a face

Answer 25

the closed walk around it

Question 26

What is the planar hand shaking lemma

Answer 26

the sum of the length of boundaries of the faces is equal to twice the number of edges.

Question 27

What is the jordan curve theorem

Answer 27

A simple closed curve in the plane divides it into two regions; one inside, one out

Question 28

What is euler’s formula

Answer 28

|V| - |E| + |F| = k + 1

Question 29

What is the limit to edges on a simple planar graph

Answer 29

|V|>=3 , then |E| <= 3|V| -6

Question 30

What is the girth of a graph?

Answer 30

The shortest length of a cycle of G

Question 31

What is a subdivision of G?

Answer 31

G with some edges divided into two or more edges by new vertices

Question 32

What is kuratowski’s theorem?

Answer 32

For finite G, G is not planar if and only if G contains a subdivison of K5 or K3,3.

Question 33

What is a platonic graph

Answer 33

A finite simple planar connected graph with all vertices of the same degree d>=3 and all faces of the same boundary length

Question 34

How many platonic graphs are there?

Answer 34

5

Question 35

What are the 5 platonic graphs?

Answer 35

tetrahedron, cube, octahedron, dodecahedron, icosahedron