Graph theory Flashcards
(22 cards)
Simple graph
No loops or multiple edges
Handshaking lemma
The total degree of a graph equals twice the number of edges
Isomorphic graph
2 graphs have one to one correspondence between their vertices
Connected graph
A path between each vertex
Euler trail
A walk that uses every edge in n the grain exactly once
A walk that uses edge once and starts and ends on the same vertex
Euler circuit
Euler theory
A connected graph had an Euler trail if it has zero or 2 vertex of odd degree
A connected graph has a Euler circuit if it has all vertices of even degree
Hamiltonian path
A path the includes every vertex exactly once
Hamiltonian cycle
A walk that includes every path exactly once and starts and ends on the same vertex
Hamilton cycle theory
Every vertex has to have a degree of 2 or more
Regular graph
All the vertices have the same degree
Cycle graph
A walk that starts and ends of the same vertex and does not repeat any vertices or edges
Complete graph
A simple graph with an edge joining each pair of vertices
Complete graph theorems
When a graph has n vertices of all the same r degree, the number of edges is (nr)/2
A complete graph with n vertices has n(n-1)/2 edges
Bipartite graph
A graph whose vertices can be divided into 2 subsets in a way that every edge of the graph joins a vertex from subset 1 to subset 2
Complete bipartite
A Bipartite graph where every vertex and s1 coins to every vertex in S2 has vertices in s1x vertices in s2 number of edges
Spanning tree
A subgraph that contains all the vertices off the original graph and is a tree
every connected graph has a spanning tree
Tree
A single, connected path between every vertex
no loops
no multiple edges
no cycles
follow edges = n-1 vertices
Planar Graph
Edges only intersect at vertices
Euler’s formula
-For any connected planar V-E+F=2
-Outside counts as 1 face
Platonic solid
A shape where each face has the same regular polygon and the same number of faces meet at each vertex. Euler’s formula applies for them.
Theorums- Lesson 4
If a simple connected graph has vertices greater then or equal to 3, has e is less then or equal to 3V-6
Any triangle free connected planar graph with vertices greater then or equal to 3 has e is less then or equal to 2v-4
