# 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.

26 views

### Graph Classification Question

I'm looking at a specific type of graph, and my google-fu has failed me. The graph $G$ is a connected unweighted directed graph where for each pair of vertices $(u,v) \in G$ the shortest path from $u$ ...
204 views

### Are edge cuts, vertex cuts, and cut sets all variously called “cuts”?

I've seen "cut" being used to refer to all three, in different places, and sometimes in the same book. Which does "cut" most commonly refer to? p.s. I am aware that "cut" itself can be defined to ...
2k views

### Do “cut set” and “edge cut” mean the same thing?

The definitions I have are: A cut set of a graph $G$ induced by a partition of $G$'s vertices into sets $X$ and $Y$ is the set of all edges with one endpoint in $X$ and another endpoint in ...
305 views

### Map-Coloring Problem

When we are faced with map-coloring problem, why do we allow countries that meet at only one point to receive the same color? Is it because they do not share the same boundaries or common boundaries? ...
136 views

### Finding maximum score in a “bubble pop” game

Consider the following game: there is a n×n field, where each cell is randomly coloured in one of m colours. Let a group of cells be a set of same-coloured cells s.t. every cell in a group has at ...
114 views

### Minimally strongly connected graphs

If $D$ is a minimally strongly connected digraph, prove that there exists a vertex with exactly one arc leaving it and exactly one arc entering it. My thoughts are to approach this with respect to ...
181 views

### What is 3-symmetric drawing of graph

i have searched through internet, but found only paid articles. Need to understand how Petersen graph can be contracted to K33, it says what through deleting the central vertex of 3-symmetric drawig. ...
223 views

### Finding the fractional vertex-cover number ($\tau ^ \star$) for k-cycle hypergraphs.

Given a hypergraph $H$, we define $\tau (H)$ to be the minimum-vertex-cover number of $H$. That is, the size of the smallest $C \subseteq V(H)$ such that $C$ meets all edges in $E(H)$. A quite ...
266 views

### Does this graph have a name?

Does graph shown below from the paper Dissection Graphs of Planar Point Sets by P. Erdos, L. Lovasz, A. Simmons, and E.G. Straus have a name? Does it come from a family of related graphs?
305 views

### How many different graphs are there of the form: $G=(V,E)$ and $V=\{1,…,n \}$.

How many different graphs are there of the form: $G=(V,E)$ and $V=\{1,...,n \}$. This is what I thought: $E$ is a set containing the lines which are $2$-element sets. There $\binom n 2$ ...
594 views

### Probability of a graph having at least 1 k-clique

I need to estimate the probability $P(\text{Graph G has at least 1 k-clique})$, any precision will do. I know the edge probability, say $p$, so the average number of the edges, $EK$, is $pm(m - 1)/2$, ...
101 views

### to find disconnected graphs

We know that if in a graph $G$, $e$ < $(n -1)$, then the graph is disconnected, where $e$ and $n$ are number of edges and number of vertices resp. Is there any other criteria to find out the ...
37 views

### is the $d$-dimensional arrangement of Trees still $NP$-hard?

The $d$ dimensional Arrangement Problem for general graphs is known to be $NP$-hard since the special case $d=1$ (OLA) already is (Garey et al, [1976]). For Trees however, the one dimensional case can ...
375 views

### PageRank algorithm. Iterative approach.

Given we have 4 nodes: A, B, C, D. A -> B and A <- B, B -> C, C -> D, C -> A and C <- A, D->A. We know only the starting probability of C which is 1. If we start from node C, what are the ...
56 views

### A graph of order $2n$ for which all vertices have degree $\geq n$ may be partitioned into adjacent pairs.

Suppose that $G$ is a graph with $2n$ vertices for which every vertex has degree at least $n$. Prove that we can partition $V(G)$ into pairs such that the two vertices in each pair are adjacent.
55 views

### Outerplanar graph

Show that for an outerplanar graph, $G =(p,q)$, where $p$ is the number of vertices and $q$ is the number of edges, $q$ is less than or equal to $2p - 3$. I tried some examples and it worked. But not ...
103 views

### Graph theory problem with friends

There are 9 people and for every 3 people, 2 of them are mutual friends. Please show that there exist 4 people out of the 9 who are all mutual friends.
157 views

### Expected number of edges: does $\sum\limits_{k=1}^m k \binom{m}{k} p^k (1-p)^{m-k} = mp$

Find the expected number of edges in $G \in \mathcal G(n,p)$. Method $1$: Let $\binom{n}{2} = m$. The probability that any set of edges $|X| = k$ is the set of edges in $G$ is $p^k (1-p)^{m-k}$. ...
65 views

### Bounding the size of a set that is a little better than a dominating set

So I am doing this problem. Let $G$ be a graph on $n$ vertices, and let $\delta>10$ be the minimum degree. I want to show that there exists a partition of the vertices $A$ and $B$ such that for ...
416 views

### How many graphs are possible on 5 vertices w/ no multiple edges or loops?

I think the answer may be $5! / (5-2)! 2!$ but I'm not sure.
61 views

### What type of graph is this?

My choices are: a) A small graph b) A directed graph c) A connected graph d) An unbalanced graph e) None of the above Now I know this isn't a small graph or ...
443 views

### Every undirected graph with $n$ vertices and $2n$ edges is connected?

I should prove this claim: Every undirected graph with n vertices and $2n$ edges is connected. If it is false I should find a counterexample. I was thinking to consider the complete graph with ...
160 views

### Question: Graph Theory and Trees

In a group of 2n schoolchildren each one has at least n friends. On an outing, the teacher tells them to hold hands in pairs. Show that this can be done with each child holding a friend’s hand, and ...
46 views

### How would $\operatorname{ir}(G)=\operatorname{r}(G)$ imply that minimal dominating is maximal irredundant?

I've read about domination theory, but I have a doubt/commentary about the following exercise from Graphs and Digraphs, 4th edition by Chartrand and Lesniak. Let $G$ be a graph with ...
56 views

### removing nodes from a regular graph

Let us assume that $G$ is $d$-regular graph. We remove $m$ nodes from $G$ at random, thus obtaining the graph $G'$. What is the degree distribution of $G'$?
398 views

### Binary heap deletion algorithm

In a binary heap ,in order to delete an element: We delete the node at the root - this is the node with highest priority. After deleting there is a hole at the root, which has to be filled, and to ...
33 views

### How can i bound the largest edge length of an $n$-point metric in $O(n)$?

For a given metric $d$ on a finite (vertex) set $V$, how can I bound the largest edge length in $O(|V|)$? While (wlog) assuming that the smallest edge length is at least $1$.
224 views

### maximum number of edges to be removed to possess a property

I am working on a problem. We know that on squaring a cycle, degree of every vertex is 4. For squares of cycles, we know if we delete any arbitrary edge then still eccentricity is same for all ...
63 views

### What's the difference between a $2$-sided and $2$-sided strip polytan

There are $14$ $2$-sided tetratans and $13$ $2$-sided strip tetratans. The sets are identical, except the square is missing in the strip version. My best guess is that for strips, no vertex can have ...
236 views

### Number of ways to hook up all vertices of a bipartite graph?

Let A represent the number of labeled vertices on the left side of a bipartite graph, and let B represent the number of labeled vertices on the right. How many ways are there to connect every vertex ...
227 views

### Menger's theorem using Hall's theorem

Can somebody help me to prove Menger's theorem for directed graphs( edge version) using Hall's matching theorem. where Menger's theorem states that: if x,y be two distinct vertices in a di-graph $G$ ...
167 views

### how to store a math problem in a binary tree?

If I have the following problem: $\ 12 - (2 +3) - (3 *4)/ (5 -7)$ How would it be stored in a binary tree? following the order of operations, would you start with $\ (3*4)$ at the top or $\ 12$ ...
35 views

### Make a partition that contains a set of points??

I am given a set of $M$ points in a segment (the edges are also points in this set) I would like to partition the segment (with equidistant points), in such a way that my partition contains all these ...
236 views

### authority distribution and hub distribution

I want to understand the concepts authority distribution and hub distribution. As I see in gephi software, Authority measures how valuable information stored at that node is. Hub measure the quality ...
96 views

### Could graph theory aid in the understanding of comparison sorting algorithms?

I am interested in computing the exact number of comparisons that are needed to sort a list. See this wikipedia article. Up to $n=15$, we know how many comparisons between elements one must make to ...
349 views

### diameter and radius of a regular graph

I am trying to find the radius and diameter of a regular graph $G$ with $d(v_i) < (n-1)/2$. I know for $d(v) \geq (n-1)/2$, $\rm{diam}(G) \leq 2$ and $\rm{radius}(G)=\rm{diam}(G).$ If we are not ...
61 views

42 views

### Definition of $\mathbb{Z}_2$-periodic graph

I see a definition of a planar, bipartite $\mathbb{Z}_2$-periodic graph, which is a graph can be embedded in the plane, the vertices can be coloured by white and black such that every edges of the ...
171 views

### Smallest nonhamiltonian 2-connected bicubic graph with chromatic index 3

I found this rather trivial example for a bicubic nonhamiltonian 2-connected graph with chromatic index 3: $\hskip0.5in$ Is this the smallest one? If not can you construct a smaller one?
160 views

### Invariance of strategy-proof social choice function when peaks are made close from solution

A question emerging from reading Schummer, J., & Vohra, R. V. (2002). Strategy-proof Location on a Network. Journal of Economic Theory, 104(2), 405–428. The setting is as follows: A finite set ...
118 views

### Graph with 5 vertices - # of spanning trees

If a graph has 5 vertices, all of them connected to each other vertex, how many different spanning trees exist? I'm thinking the answer might be $4*3*2$, because the first point has 4 options to go ...
167 views

### Is there a common notation for the labelled degree of a vertex?

Let $G$ be an undirected graph with labelled edges. The labelled degree of a vertex $v \in V(G)$ is the number of edges incident to $v$ with distinct labels. The definition of the labelled degree ...
44 views

### planar graphs of size $n \geq 2$

I'm given the problem: Let G be a planar graph of order $n \geq 2$. Prove that G has at least two vertices whose degrees are at most 5. I know, based on Euler's Formula, that $e \leq 3n - 6$ and ...
72 views

### Automorphism of Graph $G^n$

I try to define the automorphism of $G^n$ where $G$ is a graph and $G^n = G \Box \ldots \Box G$,( $n$ times, $\Box$ is the graph product). I think that : $\text{Aut}(G^n)$ is $\text{Aut}(G) \wr S_n$ ...
265 views

### Isn't seven bridges problem trivial? [closed]

What was the actual actual problem that led Euler to graph theory? By looking even at non-simplified map like this It is obvious that, if a landmass is connected by odd number of bridges, it ...
69 views

### Can more than one hamiltonian graph have the same set of hamiltonian paths?

For some pair of non-isomorphic hamiltonian graphs, can there be a chance that it be shown to have the same set of all hamiltonian paths in each graph? we get the set of all hamiltonian paths in each ...
1k views

### Why should “graph theory be part of the education of every student of mathematics”?

Until recently, I thought that graph theory is a topic which is well-suited for math olympiads, but which is a very small field of current mathematical research with not so many connections to ...
Suppose you are given a polynomial-time algorithm for the following problem related to INDEPENDENT SET: INDEPENDENT SET VALUE Input: An undirected graph $G$. Output:The size of the ...