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
114 views

¿Mathematical induction GRE math?

Im studing for the GRE math subject test...i can´t get the followin problem: Using Mathematical Induction, show that it is possible to color with only two colors the regions formed by n lines in the ...
0
votes
1answer
135 views

Determine all possible automorphisms of a graph

Let $G$ be the undirected graph whose vertex set is $\{a,b,c,d,e\}$ and edge set $\{ab, ae, bc, be, cd, ce, de\}$. The graph is drawn below: Let $V$ denote the set of vertices of the graph G ...
3
votes
1answer
112 views

Automorphism groups of self-complementary graphs

Does every self-complementary graph has a non-trivial automorphism group?
0
votes
1answer
113 views

Flip graph of point set [closed]

Is the flip graph of every point set in $\mathbb R^3$ connected? If not, is there a set with an isolated node? Def: For a point set $S$, the flip graph of $S$ is a graph whose nodes are the set of ...
2
votes
1answer
182 views

Number of graphs with vertices of only even degree. [duplicate]

This is an exercise I don't know how to solve, as I am preparing for an exam it would be great if you could help me with it. Show that for $n > 0$ a number of graphs with vertices from set ...
2
votes
1answer
346 views

Graph (or Group) in Astronomy

Is there an application of graph theory (or group theory) in astronomy. If there is, refer me some references.
5
votes
2answers
167 views

Compactness theorem, directed graph

We study a language L and the axioms of directed graphs. A directed graph is connected if there's for every 2 points a finite path. Prove that ther's no theory T such that it contains the axioms of a ...
0
votes
1answer
160 views

How many friends of friends of friends?

I'm trying to determine how many second degree (friends of friends), and third degree (friends of friends of friends) a typical individual has based on the current number of friends he or she ...
0
votes
1answer
38 views

Edge coloring question

I need your help / advice for the next question: Let $G = (V;E)$ be a 4-regular plane graph with $E = X \cup Y$ (disjoint union). For the following conditioning: For each vertex , its four ...
0
votes
0answers
188 views

Variance of the first return time of a simple random walk on an hypercube graph

I am trying to solve this problem.... I have a simple random walk on a $d$-cube (finite graph). At each vertex of the graph, the particle chooses one of $d$ edges equally likely. I need to calculate ...
4
votes
2answers
143 views

Some equivalence relation from flipping binary trees

I know almost nothing in combinatorics, so this question might be very easy, or well-known. Fix a number $n$. We will consider rooted planar binary trees with $n$ leaves. We will distinguish between ...
2
votes
1answer
61 views

Complete Graph Invariant

A graph invariant $I(G)$ is called complete if the identity of the invariants $I(G)$ and $I(H)$ implies the isomorphism of the graphs $G$ and $H$. Is there any example for complete graph invariant?
0
votes
1answer
216 views

number of digraphs where each indegree and outdegree equals 2

up to isomorphism, how many unlabeled digraphs with 5 nodes have each indegree=2 and each outdegree=2? for 3 nodes, the answer is 1 (each node points at every other node, a 3-cycle of double arrows). ...
0
votes
0answers
52 views

a doubt over a term in paper of graph theory

I was reading a paper http://www.sciencedirect.com/science/article/pii/S0166218X08001960. On the page 38, under the topic The vertex hierarchy I have doubt. From where did the following term come? ...
2
votes
2answers
56 views

Connected cubic $s$-regular graph

Let $X$ be connected cubic $s$-regular graph then $|Aut(X)| = 2^{s-1}\cdot 3\cdot |V(X)|$. I want a reference for proof.
3
votes
1answer
265 views

In every bipartite graph G, there exists a vertex v such that v is matched in every maximum matching

As a part of König's Theorem proof I have to prove following lemma: In every bipartite graph G, there exists a vertex v such that v is matched in every maximum matching. Any help?
1
vote
1answer
151 views

What does small eigenvalue gap imply for a graph?

Knowing a graph has good expansion has well-known implications. What can we say about graphs with $1-\lambda = O(\log n/n)$, where $1-\lambda$ is the difference between the two largest eigenvalues of ...
3
votes
1answer
3k views

Subgraphs of Complete graphs

I have been studying a little graph theory on my own and a simple google search has not helped so I am deciding to turn to math stack exchange. My question is: Given a complete graph $K_{n}$ where ...
1
vote
1answer
47 views

Finding path, the sum of whose numbered edges is 48

Let $G$ be a graph with vertices $\{1,\dots,10\}$. Two vertices $a,b$ have an edge if $a\mid b$ or $b\mid a$. Find a path in $G$ so that the sum of the corners in the path equals 48. I solved ...
2
votes
1answer
199 views

Counting Components via Spectra of Adjacency Matrices

I trying to implement a test for $k$-connectedness of cubic triangle-free graphs $G$ given their adjacency matrix $A$. My idea is the following: For $1$-connectedness, we construct a new graph $G'$ ...
4
votes
1answer
111 views

Bipartite subgraph having minimum degree

Prove that every graph $G$ with minimum degree $2m$ will have a bipartite subgraph having minimum degree $m$. I have tried this proof by first taking one vertex $v$ and consider it in set $D_0$. Then ...
8
votes
4answers
19k views

Prove two graphs are isomorphic

I have identified two ways of showing it isomorphic but since it is a 9 mark question I dont think i have enough and neither has our teacher explained or given us enough notes on how it can be ...
3
votes
1answer
72 views

Construction of regular graphs

What are the ways to create regular graphs using any number of vertices, under the below rule for adjacency between vertices. Rule: Vertex A is adjacent to vertex B if and only if vertex B is within ...
2
votes
1answer
41 views

doubt about my last question

I have a very basic doubt. If we talk about rooted graph, can we consider any graph whose one vertex is labeled in a special way to distinguished it from other vertices or only rooted tree. this doubt ...
0
votes
1answer
69 views

tough inequality for a graph theory problem

I am stuck at a step in a graph theory problem. I have to prove that $$ \frac{d\cdot(d-1)^k}{(d-2)} \leq d^k$$ for $d,k \geq 3$. Here $d$ actually refers to degree of a graph and $k$ the radius. The ...
0
votes
3answers
243 views

Is this the only planar cubic graph with six squares and two hexagons?

Is this the only planar cubic graph with six squares (five inside, one outside) and two hexagons? How to prove that? Allowing for multiple edges I can find another, but without not...
0
votes
1answer
70 views

$R\subset S\times S$ for $S=\{1,2,3\}$: A Graph-Theoretic Approach

So I am given the relation $R=\{(1,1),(2,2),(3,3),(1,2),(1,3)\}$ and asked which of the properties reflexive, symmetric, or transitive are held in the relation, but what I am thinking is that this can ...
2
votes
1answer
174 views

Draw a cubic planar graph with six faces of degree $4$ and one with $6$…

I'm currently playing around with Euler's Formula and found the following for cubic planar graphs: $$ \sum_{k=1}^F f_k = 6F-12, $$ where $f_k$ is the degree of the $k$th face. I tried to apply this ...
0
votes
2answers
351 views

Does a graph contain a 3-cycle or a 4-cycle

Given a graph $\mathscr G$, that has 100 nodes each with a degree can you show that this graph contains a 3-cycle and/or a 4-cycle? The graph in question represents 100 people at an event, and they ...
0
votes
0answers
78 views

Lifting automorphism problem - classical approach

Let X, Y be connected graph and Y be a covering graph of X and A be asubgroup of Aut(X). let B be lift of A. we know there is a group epimorphism from B to A. What is this epimorphism?
2
votes
0answers
88 views

How can I understand the Hadwiger conjecture?

I would like to understand the Hadwiger conjecture and I would like to read books that will allow me to both understand it and also get a grasp of the theory it is related to. Regards
12
votes
2answers
1k views

Determining the number of valid TicTacToe board states in terms of board dimension

I am attempting to find a closed form equation in terms of $n$, for the number of valid Tic-Tac-Toe board states (ignoring symmetry), where the board has dimension $n \times n ,\; 0 \lt n,\;n \in \Bbb ...
0
votes
0answers
87 views

Is there a special name for planar graphs, when the outer face has the highest degree?

Is there a special name for planar graphs, when the outer face has the highest degree? $\hskip1.3in$ Like $a)$, where $f_{\text{outer}}=6$; not like $b)$, where $f_{\text{outer}}=4$...
5
votes
1answer
83 views

Origin of the term “planar graph”

I would like to know who coined the term planar graph? I was able to trace the term back to a paper "Non-Separable and Planar Graphs" by Hassler Whitney, Proc. Natl. Acad. Sci USA. 1931 February; ...
1
vote
0answers
38 views

Embeddings and Covering faces?

I have a dude with the following problem. Suppose you have an 2-cell embedding of some simple graph $G$ on a orientable type surface $S_g$ (for example a plane graph), and you desire to find a set $A ...
1
vote
1answer
686 views

Graph Theory Question involving: Nodes, edges, degrees and paths

a) For the graph (in link above), write out the set of nodes, the set of edges, and the degree of each node. [6 marks] I have attempted this question, however wanting to find out if it is correct ...
1
vote
2answers
245 views

How well can we embed graphs with shortest path metric into $\mathbb{R}^2$ with Euclidean metric?

If we take the integer lattice in $\mathbb{R}^2$ and make edges from $(m,n)$ to $(m+1,n)$ and $(m,n+1)$, you get your typical city block street layout, and if we put the shortest path metric on the ...
1
vote
0answers
92 views

A question on graphs

Do there exist a family of graphs with $\Omega(N_{G}^{c})$ edges for some fixed $c > 0$ with the property: $$\left|\alpha\left({G \boxtimes \bar{G}}\right) - \alpha\left({\overline{G \boxtimes ...
0
votes
1answer
297 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.
1
vote
0answers
36 views

Graph class of a “polygon tree”

A cycle is a polygon tree. A new polygon tree $G′$ can be created out of an existing polygon tree $G$ by adding a cycle which shares exactly one edge with graph $G$. I want to know which graph class ...
2
votes
1answer
71 views

Are these two proofs regarding coloring valid and complete?

Question #1) Prove or disprove: If G is a graph and for every vertex $v \in V(G), \chi (G-v) < \chi (G)$, then for every subgraph H such that $H \neq G, \chi(H) < \chi(G)$. Question #2) Prove ...
11
votes
3answers
1k views

How many non-isomorphic ways a convex polygon with $n + 2$ sides can be cut into triangles?

From Wikipedia: The Catalan number $C_n$ is the number of different ways a convex polygon with $n + 2$ sides can be cut into triangles by connecting vertices with straight lines (a form of Polygon ...
2
votes
1answer
148 views

Finding the shortest/“most negative” closed directed trail in a weighted digraph with negative weights

I'm using the following definition of a "closed directed trail": a closed directed trail is a directed cycle in a digraph where all edges are distinct. Note that vertices may be repeated, so long as ...
0
votes
2answers
95 views

The strange case about the outer face…

Let $f_k$ denote the face degree of a cubic planar graph, then from Euler's Formula it follows that: $$ \sum_{k=1}^F f_k = 6F-12 \tag{1} $$ Now I tried to construct some graphs from that, so let $F=4$ ...
3
votes
1answer
153 views

Increasing the chromatic number of a graph?

The classic join of two graphs $G$ and $H$ results in $G \vee H$ whose chromatic number $\chi(G \vee H)$ = $\chi(G)$ + $\chi(H)$. $G \vee H$ = $G \cup H \cup$ Complete bipartite between vertices of ...
1
vote
0answers
87 views

A basic intuitive question on basis

From Zorn's lemma, basis can be thought of as a maximal independent set as well as minimum cover (covering all the vectors). Is this observation correct ? Can this observation be related to the usual ...
1
vote
1answer
328 views

How is percolation defined and measured in social networks?

From the wikipedia article on percolation it appears that the theory is applicable to graphs in general, and this presentation describes the theory nicely. This review article on complex networks ...
1
vote
1answer
44 views

Relationships between the tutte polynomial?

What is the relationship between a graph $G_n$ with $2$ vertices joined by $n$ edges and the graph of $C_n$ (complete graphs)? And what is the relationship between their Tutte polynomials? Tutte ...
0
votes
1answer
46 views

Let $G$ be bipartite, what is $\min\{|X_0|:\,X_0\subseteq X\,,N(X_0)=Y\}$

Let $G$ be a bipartite graph. Let $X,Y$ be the two partite sets of $G$. Suppose further that $N(X)=Y$. Consider the problem of finding: $$\min\{|X_0|:\,X_0\subseteq X\,,N(X_0)=Y\}$$ What are some ...
0
votes
1answer
39 views

Is there an algorithm for computing planar embeddings for non-biconnected graphs?

Every algorithm I've found so far begins by computing st numberings, which in turn requires a biconnected graph in order to work with an arbitrary vertex pair (s, t). In the following graph, edges ...