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

53 views

### how to count possible planar bipartitions?

i want to find out what small fraction of a solution space a metaheuristic search is actually covering. this case comes down to the number of possible bipartitions for a non-bipartite, undirected ...
102 views

### Integer hexagonal grid variations for Harborth

Harborth's conjecture states that every planar graph has a planar drawing in which all edge lengths are integers. I was looking at that, and I wondered what was known about hexagonal grid graphs. For ...
54 views

### Why $d(x) + d(y) \le n$ when proving Mantel's theorem

I was going through the Bollobás book on Modern Graph Theory. When proving the Mantel's theorem, that states $n^2/4$ is the lower-bound for having triangles, the proof start from the assumption that: ...
44 views

### If I colour $n$ vertices independently, randomly with $n^{(1-x)}$ colours, why is the size of the colour classes $(1+o(1))n^x$?

By $o(1)$, I mean 'little-o' of $1$. A paper I'm reading uses this result, but I can't see where it comes from. Thanks.
471 views

### Is it possible to uniquely number faces of a hexagonal grid with consecutive numbers?

You have a grid of regular hexagons. The aim of the game is to have each hex contain the numbers 1-6 on its edges. Each edge must also be connected to another edge that has a value one higher and ...
40 views

### Choosing which sets of nodes are 'top' and 'bottom' in bipartite graph representations of real-world complex networks.

A bipartite graph is a triplet $G=(\top, \bot, E)$ where $\top$ is the set of top nodes and $\bot$ is the set of bottom nodes, and $E\subseteq\top\times\bot$ is the set of edges. Often real-world ...
127 views

### Comparison with the greedy algorithm

Consider the following algorithm to vertex coloring: First find a maximal independent set of vertices and color these with the color 1. Then find a maximal independent set of vertices in the remaining ...
79 views

### Graph Theory Contest Maths

I have never covered Graph Theory so I've been put into a bit of a quandary over how to do these two questions (I am assuming the second is graph theory, if not I will edit it out of the question). ...
734 views

### Graph isomorphism when all vertices have the same degree

Are 2 connected graphs isomorphic if they have the same number of vertices and each vertex has the same degree $k$? I don't know how to prove it but I also can't find a counter example.
68 views

### What does $\chi(Tree)\leq 2$ mean in graph theory?

I am reading an article about graphs in English. Does $\chi(Tree)\leq 2$ mean that each node has no more then $2$ children?
129 views

### Graph theory question about planar graphs

How can i prove that every planar graph can be expressed as a union of five edge-disjoint forests ? I think I should use theorem that says : ' Every planar graph contains vertex with degree 5 or ...
62 views

### Graph theory proof about triangles.

Getting a bit stuck on this question: Prove that if any graph $H$ has $\delta (H)> \frac{n}{2}$ then $H$ contains a triangle. ($\delta (H)$ means the smallest degree of a vertex in H) So far I ...
120 views

### Are injections harder to find than surjections?

Given two finite sets $A$ and $B$ with $|A|<|B|$ There are more functions from $B$ to $A$ than from $A$ to $B$ except when $|A|=1$ or $|A|=2,|B|=3,4$. See here for proof. It is also true there are ...
125 views

### topological graph theory and the first Betti number

I am confused by a statement: in Wikipedia, In topological graph theory the first Betti number of a graph G with n vertices, m edges and k connected components equals $$m - n + k.$$ I am ...
76 views

### Geometry and natural numbers

I can't find the solution to the following problem, any help welcome. One is given a natural number N. One has to find N points on a straight line, and a (N+1)th point which is not on this straight ...
87 views

### What does the author mean in his proof “It follows by induction hypothesis” in theorem 2.3 in the given article below..

http://www.discuss.wmie.uz.zgora.pl/php/discuss3.php?ip=&url=pdf&nIdA=23384&nIdSesji=-1 What does the author mean in his proof "It follows by induction hypothesis" in theorem 2.3 in the ...
35 views

### Expected chromatic number

If $G = (V, E)$ is an undirected graph where each edge is included with probability $p \in [0,1]$ is there a way to calculate $\mathbb E[\chi (G)]$ using elementary methods? Or at least establish ...
59 views

### Longest path in $n\times n$ grid

Consider an $n\times n$ grid graph. It is easy to construct (self-avoiding) paths in it of length $n(n+2)$, by starting at the upper left corner, going downwards to the lower left corner, going right ...
317 views

### Graph Theory: A Tournament Question

First of all, this is a homework question: ...
60 views

### Tree-width of a KxK grid

It's well known that the tree-width of a $K\times K$ grid is exactly $K$. However, on the other hand, we know that the tree-width of a chordal graph is the clique number minus 1. The tree-width of a ...
54 views

### Path cover in directed graphs

I cannot figure out what this theorem is trying to say: Every directed graph G has a path cover $\mathcal{P}$ and an independent set $\{\mathcal{v}_P | P \in \mathcal{P}\}$ of vertices such ...
35 views

### Feasible method of grouping relations

This might be a bad question, I hope not so bad. Problem is I have a set of relations(millions), presumably two arrays hold two nodes(starting, and ending), which together forms a relation(edge). I ...
32 views

324 views

### Graph Theory book with lots of Named Graphs/ Graph Families

I'm doing a research about an operation on graphs and I am now in the point where I want to apply it to some named graphs or to some of the graph families like paths, cycles, wheels, etc. I am ...
34 views

### Strongly regular directed graph and its complementary graph..

I'm reading a paper (Art Duval) about generalizing the strongly regular idea to directed graphs.. anyway, the lemma is: Also, to be clear, the parameters are: $n$ - number of vertices, $k$ - valency, ...
14 views

### If $M=(E,S)$ and $N=(E,F)$ are 2 partition matroids, and $I=S \cap F$ . Is there a matroid with $I$ being its set of independent sets?

If $M=(E,S)$ and $N=(E,F)$ are 2 partition matroids, and $I=S \cap F$ . Is there a matroid with $I$ being its set of independent sets? My intuition says it's correct because $M,N$ are ...
122 views

### Examples of transient and recurrent simple random walks on trees

This is a followup to Recurrence or transience of the 1-3 tree in which I discovered that my original guess of an example for some exercises was wrong. (Those exercises can be found in http://pages.iu....
79 views

### Is there a name for graphs that only contain cliques?

I'm wondering if there is a name for graphs such that if there is an edge between vertices A and B and a second edge between vertices B and C then there must be an edge between vertices A and C. My ...
58 views

### Recurrence or transience of the 1-3 tree

The 1-3 tree is a rooted tree with only the root at level n=1, and from thereafter, $2^n$ vertices at each tier of distance from the root. However, they are not connected as in the binary tree. Put ...
252 views

### Finding the shortest cycle in a graph using every edge

Note: this is homework. Please do not give a complete answer. I've had a brief introduction in graph theory. We have been given to find a shortest cycle visiting all edges and starting and finishing ...
116 views

### Show there exists a permutation $a_{i,\sigma (i)} > \frac 1{n^2}$, Hall theorem, doubly stochastic matrix

Question: Let $A = (a_{i,j} )$ be an n by n real matrix, where n > 1, $a_{i,j}$ ≥ 0 for all i, j and the sum of elements in each row of A and the sum of elements in each column of A is exactly 1. ...
34 views

### cycle in a product of directed graphs

Does anyone know how to prove that a Cartesian product of two directed graphs $G_1 \times G_2$ has a cycle (not necessarily a Hamiltonian cycle!) if and only if one of the graphs $G_1$ or $G_2$ has a ...
81 views

### Is there any efficient progam or software to calculate the fractional chromatic number?

The fractional chromatic number $\chi_f(G)$ is a generation of the chromatic number of a graph $G$. It can be formulated as a linear programming question: Let $\mathcal{I}(G)$ be the set of all ...
39 views

### Is my induction on euler's formula sufficient? [duplicate]

$n-m+l=2$, where n=#vertices, m=#edges, l=#faces. I've been asked to demonstrate an intuitive, inductive proof (whatever the hell that means). Anyway so I've shown it's true for a tree, where ...
60 views

### Bounding the number of vertices in a graph from bellow using minimum degree and girth

I'm going through a graph theory book and apparently the number of vertices should be at least $1+\delta\sum\limits_{i=0}^{r-1}(\delta-1)^i$ for $girth=2r+1$ $2\sum\limits_{i=0}^{r-1}(\delta-1)^i$ ...
77 views

### Number of spanning trees in a wheel graph without an external edge.

How many different spanning tree contains n-element graph shown above? Determine the generating function for considered sequence. I am asking for advice.
93 views

### Finding an eigenvalue of a special cubic graph

My question is about a cubic graph $G$ that is the edge-disjoint union of subgraphs isomorphic to the graph $H$ that is as below: I want to prove that $0$ is an eigenvalue of the adjacency matrix ...
58 views

### Perfect matching in line graph

I am given a graph $T$ with an odd number greater than or equal to 3 of vertices. Its line graph $L(T)$ has exactly one perfect matching. I need to prove that if we remove any vertex from $T$, the ...
68 views

### Can $n$ vertices be removed so the directed graph contains no cycles?

Given a directed graph and $n\in \mathbb N$ how can we verify if there exists $A \subseteq V$ so that $\left | A \right | \leq n$ and $G-A$ does not contain cycles?
77 views

### connected graph with its vertices

Let $d_1 \leq d_2 \leq \cdots \leq d_n$ be the degrees of the vertices of a graph $G$, and suppose that $d_k \geq k$ for every $k \leq n − d_n − 1$. Show that $G$ is connected. I have no idea ...
54 views

### Graphgs Theory: Tree, 2 paths of maximum length intersect at a point [closed]

Justify that in a tree, 2 paths of maximum length intersect at a point.
48 views

### Graph Theory : trees, degrees and paths.

Justify that a tree with $n$ vertices that has a vertex of degree $k\gt 2$, hasn't got a path with length bigger than $n-k + 2$