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.

learn more… | top users | synonyms

1
vote
1answer
53 views

A probabilistic problem in graphs

Let $G$ be a (simple) graph. Each edge will be deleted or will be reminded with probability $\frac 12$ (independent from the other edges). Let $P_{AB}$ be the probability that (after this process) the ...
3
votes
1answer
123 views

Envy-free matching

Leg G(X,Y,E) be a bipartite graph with two equal-sized parts (|X|=|Y|=n). An envy-free matching is a matching between $X_1 \subseteq X$ and $Y_1 \subseteq Y$, such that no unmatched $x$ ($\in X-X1$) ...
2
votes
1answer
330 views

A property of graphs containing a vertex of odd degree

Let $G$ be a connected graph with at least one vertex of odd degree. Is it possible to assign $\pm 1$'s to each edge such that the for any vertex, the absolute value of the sum of the numbers on ...
1
vote
1answer
371 views

what is the maximum number of faces with n vertex in planar graphs?

what is the maximum number of faces with n vertex in planar graphs? v=number of vertices f= number of faces for example if v=3 -> max(f)=2 v=4 -> max(f)=4 (a triangle with a point in inner face of ...
1
vote
1answer
47 views

what is the maximum number of faces with m edge and n vertex in planar graphs?

what is the maximum number of faces with m edge and n vertex in planar graphs? e=number of edges v=number of vertices f= number of faces for example if v=3 -> max(f)=2 v=4 -> max(f)=4 (a ...
3
votes
2answers
303 views

Planar non-3-colorable graphs

Is it true that every planar graph that is not 3-colorable has an even wheel as a subgraph? I'm asking this because I want to prove that every outerplanar graph is 3-colorable.
-3
votes
1answer
124 views

Prove that a planar bipartite graph is a triangle-free graph

Let $g$ be a planar bipartite graph. Prove whether or not $g$ is a triangle-free graph.
0
votes
1answer
44 views

Find out the probability of a path break for an eight-hop path given that the probability of a link break is p?

Can we apply Binomial distribution here? How do I approach it? How the method will change when topology change from linear to ring topology?
3
votes
1answer
243 views

A Graph as a Union of K forests.

I want to show that a graph G that is a union of k forests has a chromatic number of at most 2k. I have narrowed my problem down to trying to show that any graph G that is a union of n trees has a ...
12
votes
3answers
370 views

A problem with 26 distinct positive integers

I am trying to solve the following problem. Assume that we are given 26 distinct positive integers. Show that either there exist 6 of them $x_1<x_2<x_3<x_4<x_5<x_6$, with $x_1$ ...
0
votes
2answers
73 views

Are edge relations always directed? Can undirected graphs have edge relations?

I have been unable to find a definition for an edge relation in a graph. I would be grateful if you could link me to an official definition for an edge relation in a graph that could answer the ...
3
votes
3answers
156 views

Can every simple graph be embedded on a circuit board?

Here, a circuit board is defined as a pair of planar graphs with vertices identified, i.e. a ordered triple $\langle V,E_1,E_2\rangle$ such that there are planar embeddings $h_1,h_2$ for the planar ...
0
votes
2answers
140 views

Existence of d-regular graphs

It is well known that if $0<d<n$ and $d\cdot n$ is even then there exist $d$-regular graphs on $n$ vertices. My question is: What is the easiest way to prove this?
4
votes
1answer
45 views

Graph with sharply 1-transitive automorphism group

What finite Graphs $G$ have the property that for all $v,w\in G$, there is exactly one automorphism $\phi$ of $G$ with $\phi(v)=w$? Of course, each of the three graphs with one or two vertices have ...
7
votes
1answer
83 views

How to list graphs systematically?

I'm working through Wilson's "Introduction to Graph Theory" and came across this question: "List all cubic graphs with at most 8 vertices". What I've done so far, is to rule out graphs with odd ...
6
votes
1answer
80 views

Graph theory , a problem

I am trying to solve the following problem: In a non-empty graph, every two vertices with the same degree do not have a common neighbor. Prove that there exists a vertex with degree one in ...
3
votes
0answers
130 views

to find the graphs having vertices with same eccentricity

I was reading a paper http://www.discuss.wmie.uz.zgora.pl/php/discuss3.php?ip=&url=plik&nIdA=11134&sTyp=HTML&nIdSesji=-1 There is a formula to calculate eccentricity in the section ...
3
votes
1answer
149 views

Is there a discrete version of non-commutative geometry (yet)?

I wonder if mathematicians have developed a discrete version of non-commutative geometry, a bit like graphs, simplicial complexes etc may be seen as a discrete version of (Riemannian) geometry (of ...
1
vote
2answers
76 views

What is the equivalent of Delaunay tringulations in high dimensions?

For 2D manifolds, Delaunay triangulation is a very useful tool for coarse graining. It has the nice property that in the flat/euclidian manifold case, it reduces to a 2D simplicial tesselation of the ...
1
vote
0answers
65 views

Does every simple cycle contain at least one back edge?

Soppose we have an udirected, connected graph. Apply the DFS algorithm to find back edges of this graph. Now, I have found a lecture notes saying following : Each back edge (i,j) defines a cycle. A ...
4
votes
4answers
97 views

What values can $v-e+f$ attain if $G$ is a planar (non connected) graph?

Let $G=(V,E)$ be a planar graph and choose planar representation. If $G$ is connected, then according to Euler's formula, we have $$v − e + f = 2,$$ were $v$ is the number of vertices, $e$ the number ...
1
vote
0answers
52 views

maximum number of pendant vertices in a graph

Can anybody help me in providing a simple hint to my problem. I was just thinking how many pendant vertices a graph can have where diameter of the graph, $diam(G)\geq3$, after leaving the graph $P_4$. ...
0
votes
1answer
113 views

Number of paths between any two vertices of Kn

Why the number of paths between any two vertices of K(n) graph is: ?
0
votes
2answers
106 views

Does this graph have a special name? (8-connected neighborhood)

Does this graph have a special name? The vertices are arranged on a square square grid with a side length of $n$ and each inner vertices has an edge to its 8 neighbors. And what about a similar ...
0
votes
2answers
107 views

Determining number of parent node on an n-tree.

I'm sorry if this is the wrong one, was unsure if this was computer science, programming, or mathematics related. I'm going with mathematics because it is semi-graph theory related. I have a tree ...
6
votes
0answers
102 views

Shortest closed loop containing all extreme points of a convex set

Suppose $S\subset \mathbb{R}^2$ is compact and convex. Suppose $\Gamma:[0,1]\to\mathbb{R}^2$ is a continuous map with $\Gamma(0)=\Gamma(1)$. Suppose $\Gamma$ passes through all extreme points of $S$. ...
1
vote
2answers
85 views

Proof - Bipartite Graphs

Let $G$ be an arbitrary, unknown graph with at least two vertices. Suppose you are given the subgraphs in the set $S = \{G - v | v \in V(G)\}$, but the vertices in the subgraphs are not labeled, and ...
1
vote
1answer
23 views

Explanation of proof about elementary properties of graphs needed.

I've come across a following document with the proof that interests me, unfortunately I'm not able to follow it. The proof is here. I completely don't get what's so contradictory about the last ...
0
votes
1answer
286 views

Number of trees with a given degree sequence.

In my quest to find the number of labeled trees with given degree sequence I've come across the following document LINK!, in which in theorem 4.3 the number of labeled trees for given degree sequence ...
1
vote
1answer
26 views

In a tree let the routes between vertices $a\to b$ and and $c\to d$ be vertex-disjoint. Show that $a\to c$ and $b \to d$ have vertices in common.

Let the route between $u$ and $v$ in a simple, connected graph be the shortest sequence of vertices, such that $[u,u_1,...,u_n,v]$ would be a way to travel a graph from vertex $u$ to $v$. In a tree ...
0
votes
1answer
81 views

2-Colorable & Decision Problem

Consider the following decision problem. Given $m$ subsets $A_{1}, \dots , A_{m} \subset \{1 , \dots , n \}$. Does there exist a subset $S \subset \{ 1, \dots ,n \}$ such that the cardinality of the ...
2
votes
1answer
83 views

Coloring a graph

I have a question about colorability of a graph. Let $G$ be an undirected graph with $n > 3$ vertices and $m$ edges = $\{(i_1 < j_1), \ldots (i_m < j_m)\}.$ Prove that we can always color ...
2
votes
1answer
52 views

eccentricity of vertices in a graph with specific operation

I was doing the following problem. Let * denote a graph operation, where $G=G_1\ast G_2\ldots\ast G_n$ with the vertex set $V(G) = \{(x_1,\ldots,x_n) : x_i\in V(G_i)\}$ and adjacency in operation is ...
1
vote
0answers
96 views

Proof of the Surfer Model Pagerank formula

How do you prove this formula for the Surfer Pagerank algorithm mathematically? ...
1
vote
2answers
115 views

Is genus of this graph bigger than 2?

Can you help me compute the genus of graph $G:$ $V(G)=\{u_1,\cdots,u_8,v_1,\cdots,v_5\}$ and $E(G)=\{u_1u_3,u_1u_4,$ $u_1u_5,u_1u_6,$ $u_1u_7,u_1u_8,$ $u_1v_2,u_1v_3, $ $u_2u_3,u_2u_4,u_2u_5,$ ...
1
vote
1answer
88 views

Gauss Elimination for Colorability Problem

Consider the following system of linear equations modulo 2: $A.X + B.Y = Z, $ where $A$ is a non-singular(modulo 2) $n$ x $n$ boolean matrix, $B $ is $n$ x $m$ boolean matrix, $X$ is n-dimensional ...
0
votes
1answer
84 views

Cycle type of induced permutation

Let $m = \binom{n}{2}$ and $S_n, S_m$ be the symmetric groups, $S_n \subset S_m$. Let $\pi \in S_n$ and let $\pi$ have the the cycle type $[λ_1,λ_2,\dots,λ_k]$, $\lambda_1+\lambda_2+ ...
2
votes
1answer
98 views

Graph Theory - Concept checking questions.

Q. Suppose $G=(V,E)$ is a simple undirected graph with no self-loop; moreover, the graph $G$ has $n=|V| ≥ 1$ vertices, $m=|E|$ edges, $k$ connected components, $p$ odd cycles, $q$ even cycles and ...
1
vote
0answers
40 views

Can a planar graph have multiple edges joining 2 vertices?

If they are planar, do the properties $2E \geq 3F$ and $E \leq 3V-6$ remain true? For example, consider 2 vertices joined by 2 non-intersecting edges. Then $E=2, F=2$ and $V=2$ and $2E \not > 3F$. ...
1
vote
1answer
115 views

Given G an Undirected Graph with > 3 Vertices(V). Prove that V Can Always be of 3 Colors Such that at Least 2/3 Edges don't Connect V of Same Color

Let $G$ be an undirected graph with $n>3$ vertices and $m$ edges. $\text{Edges} = \{ (i_{i} < j_{i}), \dots, (i_{m} < j_{m}) \}.$ Prove that we can always color vertices in 3 colors such that ...
1
vote
0answers
50 views

“Let $G$ be a planar graph. Show that every pair of vertex-disjoint odd cycles in $G^c$ is connected by an edge.” Can't figure out why “odd” matters.

If $C_1,C_2$ are vertex-disjoint cycles in $G^c$, of lengths $m,n$ respectively, not connected by an edge, then their complement has a $K_{m,n}$ minor with $m,n\geq 3$, so $G$ contains $K_{3,3}$ as a ...
1
vote
1answer
104 views

Calculate a determinant related to permutation matrix

Let $ M$ be a permutation $n \times n $ matrix and $[\lambda_1,\lambda_2, \ldots,\lambda_n]$ be the cycle type of the corresponding permutation, i.e. $ \lambda_i$ is the number of cycles of the ...
2
votes
2answers
97 views

Minimum number of elements needed from n sets

Suppose that we have n sets. They may or may not have common elements. How can we find the minimum number of elements that we should pick so that we have at least one element from each set? For ...
1
vote
1answer
60 views

How to Prove that a 3-regular bridgeless graph has perfect matching? [duplicate]

Proove that a 3-regular bridgeless graph has perfect matching?
4
votes
1answer
761 views

How to show that a self-complementary graph must have $4k$ or $4k+1$ vertices [duplicate]

How do I prove that a self-complementary graph must have $4k$ or $4k+1$ vertices?
2
votes
0answers
49 views

Puzzle - connecting nodes

This might not be the right stack exchange, so if there's a better place to put it please let me know. I have the following problem. Given the following graph, ignoring X, find all possible ...
1
vote
1answer
206 views

3-Colorability Graph Questions

I know that a boolean formula for 3-colorability is : $ \wedge_{i \in Vertices}(\bar{b_{i,1}} \vee \bar{b_{i,2}}) \wedge_{\left(i < j \right)\in Edges} ((b_{i,1} \bigoplus b_{j,1}) \vee (b_{i,2} ...
3
votes
2answers
365 views

List of ways to tell if degree sequence is impossible for a simple graph

I'm trying to make a list of ways to tell if a given degree sequence is impossible. For example $3,1,1$ is not possible because there are only 3 vertices in total so one can't have degree 3. The ...
2
votes
1answer
79 views

Smallest graph possessing a property

I was studying about Almost self-centered graphs. http://link.springer.com/article/10.1007%2Fs10114-011-9628-3 My doubt is what would be the minimum number of vertices for such graphs. My idea: I ...
0
votes
1answer
201 views

Proving that the number of leaves in a Full Binary Tree is greater than number of internal vertices

I was working on my own inductive proof and I need some feedback since I couldn't find a similar proof over Math Exchange. I've got a feeling that this proof is around where it's supposed to be but ...