# Tagged Questions

Use this tag for questions in graph theory. Here a graph is a collection of vertices and connecting edges. Use (graphing-functions) instead if your question is about graphing or plotting functions.

34 views

### Connectivity of a graph

Lets say that I have a graph that looks like this: What does it mean if I take out one node in this case $6$ is it a valid argument to say that the graph still has $6$ edges? Or that is it an ...
81 views

### Extending Euler's Formula for Connected Planar Graphs

I am trying to figure out how to extend Euler's formula, n - e + f = 2, to contain a connected component denoted k. I am new to graph theory so I am not sure if the way I got there is correct or if ...
350 views

### number of edges in the complement of a complete bipartite graph as a function of $n$, the toal number of verticies

Consider any complete bipartite graph $K_{p,q}$. Express the number of edges in $K_{p,q}^C$, the complement of $K_{p,q}$, as a function of $n$, the total number of verticies. Now, I know that I ...
39 views

### If G is connected and order = size - 1 G is a Tree [duplicate]

to prove that, is it correct to proceed by contradicion and try to reach some conclusion like "if the order = size - 1 there can't be any cycles"? In that case, can you give me a hint of where to ...
68 views

### The connectivity of a graph does not exceed its minimum degree

Prove that for every graph $G: \mathcal K(G) \le \delta G$ $\mathcal K(G)$ is the connectivity of $G$ $\delta G$ is the minimum degree of $G$ This is a theorem in Graph Theory that I believe needs ...
91 views

76 views

325 views

### Graph theory : How to find edges ??

A simple graph in which each pair of distinct vertices is joined by an edge is called a complete graph. We denote by Kn the complete graph on n vertices. A simple bipartite graph with bipartition (X,Y)...
54 views

### Long induced path containing a lot of vertices from a stable set

Is there a simple proof/counter-example for this? If we have a (big) connected graph $G$ with a big stable set $S$ and with bounded maximum degree (read "small"), then there's a long induced path (...
178 views

### Prove thoroughly: If the degree of all vertices is greater or equal to $\frac{|V| - 1}{2}$, then the simple graph is connected.

I am struggling to write a good, thorough proof. The proof is supposed to be logically rigorous, correct and complete (e.g. no hidden assumption). Moreover, style is important - the proof should be ...
87 views

### Why do the children of a node $n$ in a complete binary tree have indices $2n$ and $2n+1$?

The complete binary tree is breadth-first ordered 1 to $n$ where $n$ is the number of nodes. The thing I cant seem to understand is that why are the children of node $N$ always $2N$ and $2N+1$? For ...
43 views

### What are some non planar graphs whose sequence is $(4\,4\,3\,3\,3\,3)$?

I know that in order for the $6$-vertex graph to be non planar, it needs to contain more than $12$ edges. I tried drawing some picture to find the graph, but run out of ideas. It's easy to find the ...
210 views

### Graph Theory using Rectangles

Show that it is impossible, using 1x2 rectangles, to exactly cover an 8x8 square from which 2 opposite 1x1 corner squares have been removed. When I do this on paper, it is clear that it is not ...
72 views

### Number of labeled graphs of $n$ odd degree vertices

Counting graphs with even degrees! Trouble with formula! This question is about number of labeled graphs of $n$ even vertices. I need hint how to find number of labeled graphs of $n$ odd degree ...
37 views

### Geodesic distance in graphs

I'm reading a paper that deals with networks/graphs. In the paper they mention the term 'geodesic distance'. I'm not able to understand what does it mean. I hope if you can explain it to me.
93 views

215 views

### Proving this property of a tournament graph by induction?

I am working on practicing proofs by induction. Can you please take a look at the proof below and tell me if I proved it correctly? I am particularly worried about the inductive step. Definition 1....
60 views

118 views

### Proof that G - v is a tree

For school we have the following assignment: Let v be a leaf of graph G. Prove that the following two statements are equivalent: (i) G is a tree, and (ii) G - v is a tree. The first thing I ...
260 views

### Expectation number of cycles in a Erdős–Rényi random directed graph $G(n,p)$

Let $G \sim G(n,p)$ be a directed Erdős–Rényi random graph with $n$ vertices and the probability $p$ that there is a directed edge between any two ordered pairs of vertices. What is the expected ...
280 views

### Cayley's formula for the number of trees(Recursion)

I'm trying to understand the proof by recurcion and induction for the Cayley's formula for the number of trees.While I'm trying to understand it there are some things that I don't get at all. -It ...
66 views

### find an algorithm to find MST in linear time while each edge has the same weight

I have been disscussing this problem with a lot of my friends . However no solution has been found. let G= w is a weight function for each e in E w(e)=1 find MST of G in O(|V|+|E|) thanks
66 views

### Degeneracy number of a ring graph

The definition of $k-$ degeneracy is not clear to me. Could someone please explain how is degeneracy number different from maximum degree $\Delta G$ of the graph $G$? And second question is, does a ...