Basic Graphs Flashcards
1
Q
Graph?
A
2
Q
Simple graph?
A
3
Q
Petersen graph?
A
4
Q
d(v) is?
A
5
Q
If graph G is simple then d(v) is?
A
6
Q
Max degree of any vertex in G?
A
7
Q
Minimum degree of any vertex in G
A
8
Q
A
9
Q
A
10
Q
A
11
Q
To show the two graphs are not isomorphic
A
12
Q
Complete graph
A
13
Q
Number of edges, in complete graph
A
14
Q
Two vertices are adjacent if?
A
15
Q
A walk from u to v
A
16
Q
Trail
A
17
Q
Path
A
18
Q
Cycle
A
19
Q
A
20
Q
Graph G is connected if
A
21
Q
A
22
Q
A component of a graph G is
A
23
Q
Disconnecting set
A
24
Q
Cutset
A
25
If anyone of the edges in a cutset is retained
Graph stays connected
26
If a cut set consist of a single edge
The edge is called a cut edge, or a bridge
27
Separating set
28
Separating set that consists of single vertex
Cut vertex
29
Tree
Connected graph with no cycles
30
Bipartite graph
31
A graph is bipartite, if
And only if there are no cycles of odd length
32
33
Prove that G contains a cycle
34
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
35
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
36
A connected graph is semi eulerian if
And only if it has at most two vertices of odd degree
37
38
A connected graph is Hamiltonian, if
39
Gabriel dirac’s, theorem
40
41
A forest?
Graph whose connected components are trees
42
f(n,s)?
Number of forests , G, with n vertices and exactly s connected components
=n^(n-s-1)
43
Number of trees of n vertices?
n^(n-2)
44
eulerian trail?
a tour or a closed trail which includes every edge of G
45
Degree of vertices of W_n?
One vertex of n-1 degree and all others degree 3
46
Degree of vertices of C_n?
2 for all vertices
47
Degree of vertices in K_n?
Every vertex has degree n-1
48
A complete graph G with n vertices has how many edges?
49
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
50
And acyclic graph on n vertices has at most ? Edges
N-1
51
Gabriel, dirac’s theorem
52
Geometric graph
Any 2 e€E are disjoint or have one of their endpoints in common
(no crossing over)
53
Euler’s formula
For any connected planar graph we have n - e + f = 2
f is # of faces
54
The girth of a graph?
For a graph containing cycles, this is the length of the shortest cycle
55
Bridge?
For a connected graph G, this is the urge to stops it from being connected when removed
56
G be a connected planar graph on n vertices, if G is acyclic?
Then G has precisely n-1 edges
57
G be a simple connected planar graph on n vertices, if G has girth atleast g?
Then G can have a most
58
Let G be a connected planar graph with N vertices, n>=3, then?
G contains at most 3N-6 edges
59
Two standard graphs that are not planar
K_5 K_3,3
60
Edge contraction ?
Relive edge and merge all endpoint vertices into one vertex
61
Edge expansion
Opposite of edge contraction, add new vertex and connect to end points of existing edge
62
2 graphs are homeomorphic if
One can be obtained from the other by a sequence of edge, contractions and expansions
63
Subdivision of a graph G
A graph that can be derived from G by a series of edge contractions
64
A graph is planar iff?
And only if it does not contain a sub graph homeomorphic to K_5 or K_3,3 (Wagner)
65
For a planar graph G drawn on a plane surface S, S’ is?
Surface obtained by removing all line segments in E
66
A plane graph is
A graph G can be drawn in R^2 without crossings so edges only intersect in vertices
