Graph theory Flashcards
What is a simple graph?
A simple graph G is a pair of sets G(V,E) such that each element E is a 2 element subset of V.
What is the n-cube graph? (Qn)
It is a graph formed from the vertices and edges of an n dimensional hype cube.
What is the hand shaking lemma?
For any graph, the sum of the degrees of the vertices is equal to twice the number of edges.
What is the definition of isomorphism
Two simple graphs are isomorphic if there exists a bijection which preserves adjacency.
What is the compliment of G?
It is the graph which has all the other possible edges.
What is a walk?
It is a sequence of vertices and edges with vi and ei not necessarily distinct. v1,e1,v2,…,vk-1,ek-1,vk
What is the length of a walk?
k-1
what is a closed walk?
A walk in which the first vertex is equal to the last.
what is a trail?
A walk with no edges repeated
what is a circuit?
A closed trail.
what is a path?
A walk with no vertex repeated
What is an n-cycle?
A cycle with n vertices and so n edges
What is lemma 2.1
If a graph G has a walk from vertex v to vertex w, v≠w then G has a path from v to w.
What is lemma 2.2
if every vertex in a finite graph has degree >1 then G contains a cycle
what is a connected graph>
One in which given a v,w in V, there is a path from v to w.
What is an unconnected graph
One with two or more unconnected components
What is a bridge
An edge whose removal will increase the number of connected components.
What is a euler circuit
A circuit using each edge exactly once.
What is a graph with a euler circuit called
Eulerian
What is euler’s theorem
Let G be a finite connected graph. Then G has a euler circuit if and only if all vertices are of even degree.
What is lemma 2.5
If G is finite connected with all vertices of even degree, then G is a finite union of edge disjoint cycles.
What is a bipartite graph
Suppose V=V1⋃V1 and V1∩V2=∅ and every edge has one end in V1 and one end in V2
What is a planar graph
One which can be drawn in the plane so that no edges meet except at their end points.
What is a face
They are the regions which a planar representation of a graph divides the graph into
What is the boundary of a face
the closed walk around it
What is the planar hand shaking lemma
the sum of the length of boundaries of the faces is equal to twice the number of edges.
What is the jordan curve theorem
A simple closed curve in the plane divides it into two regions; one inside, one out
What is euler’s formula
|V| - |E| + |F| = k + 1
What is the limit to edges on a simple planar graph
|V|>=3 , then |E| <= 3|V| -6
What is the girth of a graph?
The shortest length of a cycle of G
What is a subdivision of G?
G with some edges divided into two or more edges by new vertices
What is kuratowski’s theorem?
For finite G, G is not planar if and only if G contains a subdivison of K5 or K3,3.
What is a platonic graph
A finite simple planar connected graph with all vertices of the same degree d>=3 and all faces of the same boundary length
How many platonic graphs are there?
5
What are the 5 platonic graphs?
tetrahedron, cube, octahedron, dodecahedron, icosahedron
