Basic Graphs Flashcards
Graph?
Simple graph?
Petersen graph?
d(v) is?
If graph G is simple then d(v) is?
Max degree of any vertex in G?
Minimum degree of any vertex in G
To show the two graphs are not isomorphic
Complete graph
Number of edges, in complete graph
Two vertices are adjacent if?
A walk from u to v
Trail
Path
Cycle
Graph G is connected if
A component of a graph G is
Disconnecting set
Cutset
If anyone of the edges in a cutset is retained
Graph stays connected
If a cut set consist of a single edge
The edge is called a cut edge, or a bridge
Separating set
Separating set that consists of single vertex
Cut vertex
Tree
Connected graph with no cycles
Bipartite graph
A graph is bipartite, if
And only if there are no cycles of odd length
Prove that G contains a cycle
A connected graph is semi
Eulerian, if
- And only if it has at most two vertices of odd degree
-There is a trial, which includes every edge of the graph
A connected graph is eulerian if
and only if each vertex has even degree <=> the edge set of G can be partitioned into cycles <=> there is an eulerian trail
A connected graph is semi eulerian if
And only if it has at most two vertices of odd degree
A connected graph is Hamiltonian, if
Gabriel dirac’s, theorem
A forest?
Graph whose connected components are trees
f(n,s)?
Number of forests , G, with n vertices and exactly s connected components
=n^(n-s-1)
Number of trees of n vertices?
n^(n-2)
eulerian trail?
a tour or a closed trail which includes every edge of G
Degree of vertices of W_n?
One vertex of n-1 degree and all others degree 3
Degree of vertices of C_n?
2 for all vertices
Degree of vertices in K_n?
Every vertex has degree n-1
A complete graph G with n vertices has how many edges?
K_n,m
The complete bipartite graph where |V_1| = n and |V_2| = m and every vertex in V_1 is adjacent to every vertex in V_2
And acyclic graph on n vertices has at most ? Edges
N-1
Gabriel, dirac’s theorem
Geometric graph
Any 2 e€E are disjoint or have one of their endpoints in common
(no crossing over)
Euler’s formula
For any connected planar graph we have n - e + f = 2
f is # of faces
The girth of a graph?
For a graph containing cycles, this is the length of the shortest cycle
Bridge?
For a connected graph G, this is the urge to stops it from being connected when removed
G be a connected planar graph on n vertices, if G is acyclic?
Then G has precisely n-1 edges
G be a simple connected planar graph on n vertices, if G has girth atleast g?
Then G can have a most
Let G be a connected planar graph with N vertices, n>=3, then?
G contains at most 3N-6 edges
Two standard graphs that are not planar
K_5 K_3,3
Edge contraction ?
Relive edge and merge all endpoint vertices into one vertex
Edge expansion
Opposite of edge contraction, add new vertex and connect to end points of existing edge
2 graphs are homeomorphic if
One can be obtained from the other by a sequence of edge, contractions and expansions
Subdivision of a graph G
A graph that can be derived from G by a series of edge contractions
A graph is planar iff?
And only if it does not contain a sub graph homeomorphic to K_5 or K_3,3 (Wagner)
For a planar graph G drawn on a plane surface S, S’ is?
Surface obtained by removing all line segments in E
A plane graph is
A graph G can be drawn in R^2 without crossings so edges only intersect in vertices
