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

0
votes
0answers
6 views

Variation of TSP - Revisit Nodes

I have a problem where I have an symmetric graph and I want to find that shortest path that visits every node at least once (not exactly once). In order to solve this problem, I have found that we ...
1
vote
1answer
16 views

A graph whose vertices all have degree $2$ must contain a cycle

I've been working on some beginner graph theory, and I was having some funky issues with this particular problem. Consider a graph $G$ such that for all $x \in V(G),\, \deg(x) = 2.$ I want to prove ...
0
votes
0answers
11 views

In a maximal planar graph, are two consecutive neighbors of a vertex necessarily adjacent?

If we pick a vertex $v$ and two consecutive neighbors of it, $u_1$ and $u_2$, are we sure that $(u_i, u_{i+1}) \in E$? My intuition is that if $(u_1, u_2) \notin E$, you can add an edge by going from ...
0
votes
1answer
12 views

prove that the minimum number of trails in an odd graph is n/2

In my HW assignments I was asked to prove that If a graph G consists of only odd degree vertices, then the minimum number of trails that decompose it (without having any common edge between each two ...
0
votes
0answers
8 views

An extemal combinatorial design question. “Weak” steiner stystems.

A Steiner system $S(t,k,\nu)$ is a collection $X$ of $\nu$ points and a collection of subsets of $X$ of size $k$ (frequently called blocks) such that each $t$ element subset of $X$ occurs in exactly ...
11
votes
1answer
5k views

Proof : cannot draw this figure without lifting the pen

This question maybe ridiculous but I always found it interesting... Here it is : (I cannot put image so I put you the link of the pictures) When I was in school I used to draw houses when I was bored ...
0
votes
0answers
10 views

Prove if $G$ and $H$ are graphs on the same vertex set, then $dg(G∪H)≤dg(G)+dg(H)$

Prove if $G$ and $H$ are graphs on the same vertex set, then $dg(G∪H)≤dg(G)+dg(H)$ $dg(G)$ is the the minimum k such that $G$ is k-degenerate. I know it can be proved with respect to graph coloring, ...
0
votes
2answers
28 views

Polyhedron with 12 pentagons and 1 hexagon

In this answer http://mathoverflow.net/a/19823/5239, it is indicated that it is impossible to make a polyhedron (with 3 faces meeting at each vertex) out of 12 pentagons and 1 hexagon. There is ...
12
votes
4answers
686 views

Double obstructing wall problem, what is the optimal walk path and length?

Every day, you walk from point A to point B which are exactly $2$ miles apart straight line distance, however, each day, there is a $50$% chance of there being an obstructing wall perpendicular to the ...
0
votes
0answers
18 views

What is the Code in mathematica for getting a graph with following condition? [on hold]

Let X=(V(X),E(X)) is a graph with following properties. It's an undirected graph. Contains isolated vertex,{1} in E(X). Graph need to be labeled with V(X). Vertex Style is circular with labeling ...
0
votes
0answers
15 views

How to find the eigen values

How to find the eigen values of the graph having vertex set as $\{1,2,.......n\}$ and edge set as $\{(I,I+1)\}$ $ \cup (1,n)$ ? where $1\le l \le n$. Here I am considering the Laplacian matrix of ...
2
votes
0answers
13 views

Quotient of a graph and digraph? What are the equivalence classes of a graph?

I want to understand quotient of a graph (also called quotient graph), my teacher says that the terms quotient of a graph and a modulo of a graph should be synonyms (even though modulo of a graph ...
1
vote
0answers
17 views

Quasi-Group represented by a graph which is not a Triangle-Free Graph locally

Can each of all quasi-groups be represented by a graph (latin square graph), which is not locally triangle free graph ? Quasi Group can be represented by Latin Square matrix, thus by a Latin ...
0
votes
1answer
75 views

Can a triangle free graph represent a Group?

Some facts are- Group can be represented by a graph. Group Isomorphism $\leq_p$ Graph Isomorphism. Under this context, my questions is- Can a triangle free graph represent a group? Edit: My ...
0
votes
0answers
24 views

How to count all cycles (simple or not) in a directed complete graph?

I came up with an algorithm for counting cycles (simple or not) of length less or equal to n in a given directed complete graph Kn. I am looking for a more concise way of counting cycles but have not ...
0
votes
0answers
7 views

Network with more than one maximum s-t flow

I'm struggling to think of an example of a network with more than one maximum s-t flow. In addition, is there an efficient way to identify whether or not a network has a unique maximum s-t flow?
1
vote
2answers
40 views

What's the most efficient algorithm to check the number of cycles of length 4 in an undirected graph?

What's the most efficient algorithm to check the number of cycles of length 4 in an undirected, unweighted graph?
1
vote
3answers
28 views

proof about hall's theorem in graph theory

Prove that a k regular bipartite graph has a perfect matching by using hall's theorem. Approach Let S be any subset of the left side of the graph The only thing I know is the number of things ...
0
votes
0answers
8 views

Neighborhood structure in a uniform hypergraph

Consider a $k$-uniform connected hypergraph with vertex set $V$ and hyperedge set $E$, as defined in https://en.wikipedia.org/wiki/Hypergraph#Symmetric_hypergraphs . We impose the following condition ...
1
vote
0answers
16 views

HM question- the graph K4,3

We've been asked to prove the following: Prove that you can place K4,3 on the plane with exactly two intersects. then, prove that you can't do it with less intersections. someone?
1
vote
0answers
25 views

What is an algorithm for finding the shortest path in a graph that crosses each edge at least once.

I am looking for an algorithm that, given a graph, finds the shortest (or approximately shortest) path that crosses all edges at least onces. (Multiple times crossing an edge is allowed!) The graph ...
1
vote
1answer
197 views

Bound on the size of Permutation Set for Isomorphism

$\textbf{Claim :}$ $G, H $ are partitioned into sub-graphs $\{ G_1,G_2 \cdots G_x \}$ and $\{ H_1,H_2 \cdots H_x \} $ . For each $G_i$ we constructed a set permutation, $\beta_i$ such ...
0
votes
0answers
27 views

Why must every bridge in an Eulerian walk/circuit be traversed twice? (Chinese Postman Problem)

Does it have to do with the degrees of the vertices? The book I was reading has this as a theorem but doesn't include the proof for some reason. This was in the context of the Chinese Postman Problem. ...
1
vote
1answer
10 views

Duality theorem between Cycle Space and Cut Space in terms of Matrices?

The book Graphs and Matrices by Bapat formulates linear algebra on graph theory, yet I cannot find important theorems such as Duality theorem between the cycle space and the cut space (Diestel p.26, ...
0
votes
2answers
67 views

Preferential Attachment and salton similarity in directed networks

Preferential Attachment similarity between two nodes in an undirected graph is the degree of the first node multiplied by the degree of the second node. But what about directed graphs? Which degree ...
1
vote
1answer
21 views

Euler formula. 100 faces

can you give any clue to this task: I have polyhedron with 100 faces, in which 50 are triangles and 50 rectangles. Prove that at least one of vertices has degree $\ge 5$.
0
votes
0answers
40 views

Propositional formulas for connected graph

I have some difficulties with the following problem. Let $G = (V,E)$ be a graph with $V = \mathbb N$ (natural numbers) and $E \subset \mathbb N^2$. Let $p_{ij}$ be a set of propositional ...
6
votes
3answers
2k views

Spanning Trees of the Complete Graph minus an edge

I am studying Problem 43, Chapter 10 from A Walk Through Combinatorics by Miklos Bona, which reads... Let $A$ be the graph obtained from $K_{n}$ by deleting an edge. Find a formula for the number ...
1
vote
0answers
21 views

Number of Vertices with $\mu$ Common Neighbor

$\mathcal{G}$ is a graph class. Each graph $G$ of $\mathcal{G}$ has the following properties- $G$ is a $k$ (variable with respect to different graphs) regular graph of $n$ vertices. The vertex set ...
1
vote
1answer
40 views

Graph with exactly one perfect matching

How do I prove that if $ G $ graph, with $2n$ vertices, has exactly one perfect matching then $ |E(G)| \le n^2 $ ?
8
votes
1answer
409 views

What is the probability that a random $n\times n$ bipartite graph has an isolated vertex?

By a random $n\times n$ bipartite graph, I mean a random bipartite graph on two vertex classes of size $n$, with the edges added independently, each with probability $p$. I want to find the ...
0
votes
1answer
400 views

Algorithm of creating dual graph from a plannar graph

Depite i have some ideas to create a dual graph from a planar graph, but i prefered to ask it here. Is there any algorithm for this purpose? Thank you so much.
0
votes
1answer
14 views

Large cycles in bridgeless cubic graphs

Wikipedia tells us that most cubic graphs have a Hamilton cylce (for instance the proportion of Hamiltonian graphs among the cubic graphs on $2n$ vertices converges to 1 as $n$ goes to infinity) but ...
1
vote
0answers
19 views

Derive Hall's theorem from Tutte's theorem

I'm trying to derive: Hall Theorem A bipartite graph G with partition (A,B) has a matching of A $\Leftrightarrow \forall S\subseteq A, |N(S)|\geq |S|$ From this: Tutte Theorem A graph G has a ...
0
votes
0answers
12 views

Finding δ(s,v) for all v∈V , when given zero weighted cycle edges- in linear time

Formally: Let it be $G=(V,E)$ directed graph with a weight function $w: E -> R $. Let it be $s∈V$ (source vertex). For all $e∈E$ so that $e$ belongs to a cycle in G, $w(e)=0$ (if $e$ doesn't ...
1
vote
1answer
61 views

Decomposition of graph to cycle and cut space

Let $G$ be a graph. I want to show that $E(G)$ is disjoint union $C\cup D$ where $C$ and $D$ belong to cycle and cut space respectively.
1
vote
0answers
13 views

The existence of a cycle in a graph

Let C and D will be different cycles in the graph G, and e - common edge to the cycles of C and D. Show that a graph G contains a cycle not passing through the e. I think, it's not easy task, because ...
0
votes
0answers
12 views

$k$-regular connected graph with no perfect matching

How do I construct a $k$-regular connected graph with no perfect matching? I know that if $G$ is $k$-regular bipartite graph it has perfect matching, so the graph that I'm looking for shouldn't be ...
0
votes
2answers
16 views

Is this triangulation consistent with Sperner's Lemma?

Since any two triangles which intersect have an edge or a vertex in common, the triangulation is simplicial. However, I am concerned about triangle $A$. Is every sub-triangle supposed to have a ...
2
votes
1answer
82 views
+50

Train networks on which every point is visited after a finite time

I am looking for the set of all train networks fulfilling the following property: There is a maximum time after which a moving train revisits each part of the track, no matter what turn it takes at ...
3
votes
0answers
118 views

Odd problem about graph connectivity

This problem asks how to prove that a graph has $k$-connectivity. However, there's something which makes the problem intricate. The graph which I'm studying about is a graph with $2k-2$ vertices and ...
0
votes
1answer
29 views

Upper bound on the list chromatic number of $d$-degenerate graphs

It can be proved that $\chi(G)\le d+1$ if $G$ is $d$-degenerate, but can we also say that $\chi_\ell(G)\le d+1$, in general[note 1]? Here, $\chi(G)$ is the chromatic number of $G$ and $\chi_\ell(G)$ ...
0
votes
0answers
11 views

Upper bound for a graph related finite sum

At the moment I am looking into undirected graphs $G=(V,E)$ with node set $V=\{1,\ldots,M\}$ and edge set $E$. We can assume that they are connected by the way. Lets denote edges from $i$ to $j$ by ...
0
votes
1answer
39 views

Total Chromatic Number of Cycles

According to Wikipedia, In graph theory, total coloring is a type of graph coloring on the vertices and edges of a graph. When used without any qualification, a total coloring is always assumed to be ...
2
votes
2answers
496 views

Give an algorithm that computes a fair driving schedule for all people in a carpool over $d$ days

Some people agree to carpool, but they want to make sure that any carpool arrangement is fair and doesn't overload any single person with too much driving. Some scheme is required because none ...
2
votes
2answers
36 views

Construct a non-Hamiltonian Graph

How do I constuct a $G$ non Hamiltonian graph for any $n≥3 $ $( |V(G)|=n )$, in which $\delta(G)$ is at least $(n-1)/2$? Is there any algorithm for that? Do I have to use mathematical induction? When ...
1
vote
1answer
43 views

Describe 3-colourable graph in propositional calculus

I am trying to solve the following problem. Let $G=(V,E)$ be a Graph with $V=N$ (natural numbers) and $p_{ij}$ a set of propositional variables for which we have $p_{ij}$ is true <=> $(i,j)\in E$. ...
0
votes
0answers
41 views

Prove that the set of matrices $\{I,A,A^2,\ldots A^m\}$ is linearly independent.

Let $A$ denote the adjacency matrix of a connected graph $G$ with $n$ vertices and $e$ edges.If $i $ and $j$ are vertices of $G$ with $d(i,j)=m$. Then prove that the set of matrices ...
1
vote
1answer
24 views

How do I rearrange an adjacency matrix of an acyclic digraph so its non-zero elements are above the diagonal?

Any graph can be represented by an adjacency matrix. The matrix for an acyclic digraph can be represented as a matrix with all its non-zero elements above the diagonal. However, if I were to take an ...
1
vote
0answers
27 views

Clarification of Sperner's Lemma

From Graph Theory by Bondy, Murty Image from wikipedia I don't see how the picture holds according to the definition from the Graph Theory book. Specifically, the definition says to assign ...